\documentclass[a4paper,12pt]{report}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel} 
\usepackage{graphicx}
\usepackage{caption}
\usepackage{longtable}

\usepackage[table]{xcolor}
\usepackage{pdfpages}

\begin{document}


% % \title{Tesis de Licenciatura en Ciencias de la Computación}
% \title{Competencias de programación}
% \author{
% Nicolás Alvarez\\
% Director: Pablo Fillotrani
% }
% % \maketitle
% \maketitle

% ---------------Nueva Portada---------------
%\definecolor{steelblue}{rgb}{0.27,0.51,0.71}

\thispagestyle{empty}
\begin{center}
	\begin{tabular}{c b{10cm} c}
		\includegraphics[width=50px]{img/depto.png}
	&
	
		\begin{center}
			\begin{tabular}{c}
				Departamento de Ciencias e Ing. de la Computación\\
				Universidad Nacional del Sur
			\end{tabular}
		\end{center}
	
	&			
			\includegraphics[width=50px]{img/uni.png}
	\end{tabular}
\end{center}

\vspace{4cm}

\begin{center}

  {\large Tesis de Licenciatura en Ciencias de la Computación}\\[1.0cm]%[1.25cm]
  {\LARGE Competencias de programación}\\[5.5cm]


{\large Nicolás Alvarez\\
Director: Pablo Fillotrani\\[2cm]
Bahía Blanca, Argentina, 2011\\}
\end{center}

% ------------- Abstract ------------------
\begin{abstract}
En este trabajo nos proponemos ofrecer una guía para aquellos interesados en participar en competencias de programación.
Haremos una descripción general de las principales competencias de programación, así como un análisis comparativo entre las mismas.
Nos enfocaremos principalmente en la competencia ICPC (International Collegiate Programming Contest) organizada por la ACM (Association for Computing Machinery).
Propondremos estrategias para entrenar, trabajar en equipo y coordinar tareas en entornos de competencias de ACM ICPC.
Mostraremos algunos ejemplos de problemas de competencias pasadas, con las soluciones correspondientes.
Por último, proveeremos al lector de detalles de implementación útiles a la hora de programar en competencias de algoritmos.

% Partiendo de una categorización de problemas típicos en estas competencias, haremos foco sobre un tópico específico en cada sección.
% Las secciones constarán de una explicación introductoria y luego se propondrán ejemplos de problemas de competencias pasadas, con soluciones explicadas y código fuente.
% Por último, proponemos estrategias para trabajar en equipo y coordinar tareas en entornos de competencias de ACM ICPC.
\end{abstract}

% ------------- TOC ------------------
%\newpage
\tableofcontents

% Comandos y ambientes
\newcommand{\titulo}[1]{{\noindent\large\em #1 \newline}}
\newcommand{\subtitulo}[1]{{\noindent\bf #1}}

\newcommand{\inoutsamples}[2]{    
     \vspace{1\baselineskip}
     \begin{tabular}{|l|l|} \hline
          \textbf{Sample input} & \textbf{Output for sample input} \\ \hline
          \begin{minipage}[t]{0.45\textwidth} \texttt{#1} \vspace{1ex} \end{minipage} & \begin{minipage}[t]{0.45\textwidth} \texttt{#2} \vspace{1ex} \end{minipage} \\ \hline
     \end{tabular}}

\newcommand{\libro}[4]
{\bigskip
\begin{tabular} { l l } 
  \begin{minipage}{0.5\textwidth}
    \subsection*{#1 \\
    \normalsize #2 \\
    \small #3}
  \end{minipage}
&  
  \begin{minipage}{0.5\textwidth}
    \hspace{2ex}
    \includegraphics[height=4cm]{#4}
  \end{minipage}
\end{tabular}
\bigskip
}

\definecolor{light-gray}{gray}{0.85}

\newenvironment{xtabular}[1]
{\rowcolors{0}{light-gray}{white} \begin{tabular}{#1} \hline } 
{ \hline \end{tabular} }

\newenvironment{fullindent}[1]%
{\begin{list}{}%
  {\setlength{\leftmargin}{#1}}%
  \item[]%
}
{\end{list}}


\newcommand{\probtitle}[1]{\subsection*{#1}}
\newcommand{\probsub}[1]{\subsubsection*{#1}}
\newenvironment{problema}
{%
\setlength{\parindent}{0cm}
\begin{center}
\begin{tabular}{| l |}
\hline
\begin{minipage}{0.95\textwidth}
\medskip
}
{%
\bigskip
\end{minipage}
\\ \hline
\end{tabular}
\end{center}
}
 
% \newenvironment{problema}
% {
% \setlength{\parindent}{0cm}
% {\noindent\rule{\linewidth}{0.5mm}}
% }
% {{\noindent\rule{\linewidth}{0.5mm}}}


\chapter{Introducción}

\section{Antecedentes}

En la actualidad existen numerosas competencias de algoritmos que poseen diferentes características y están orientadas a distintos niveles educativos 
(secundario, universitario, abierto). Entre éstas se destacan, a nivel secundario, la {\em International Olympiad in Informatics} y, a nivel universitario,
la {\em International Collegiate Programming Contest} (ICPC) \cite{icpc} organizada por la {\em Association for Computing Machinery} (ACM) \cite{acm}.
\newline

La ICPC es una competencia de múltiples etapas auspiciada por ACM, se participa por equipos de 3 estudiantes de una misma universidad.
La competencia involucra una red de universidades alrededor de todo el mundo que organizan instancias regionales para clasificar a los mejores equipos a
la Final Mundial. 

La IOI se organiza anualmente desde 1989, fue propuesta por la UNESCO y es una de las 5 olimpiadas internacionales académicas para estudiantes secundarios.
Su principal objetivo es estimular el interés en las ciencias de la computación a nivel mundial.
\newline

La participación en ACM ICPC ha crecido hasta alcanzar a decenas de miles de estudiantes de computación de casi 2000 universidades provenientes 
de 80 países. Por otro lado, la IOI reúne cada año delegaciones nacionales de hasta 4 participantes provenientes de 81 países.

Existen otras competencias de gran envergadura como Topcoder, Google Code Jam y Codeforces que también convocan un gran número de participantes y que
se han ido expandiendo rápidamente en estos últimos años.
\newline

La importancia de estas competencias radica en que provee a los estudiantes la chance de desarrollar habilidades que no suelen ser fomentadas
en la formación académica tradicional, resultando una actividad complementaria muy enriquecedora a nivel personal y profesional.

Por un lado, fomentan en sus participantes la creatividad, cooperación, innovación y permite a los estudiantes probar sus habilidades
para trabajar bajo presión. Otro aspecto importante de estos certámenes es lograr reunir a estudiantes de todo el mundo para que puedan compartir 
experiencias científicas y culturales.

\section{Metodología}

Para realizar este trabajo se apelaron a diferentes fuentes, entre las que se encuentran libros, publicaciones, sitios web, manuales de referencia, 
archivos de problemas y, tal vez la más importante, la experiencia adquirida durante los años de participación en competencias de programación y de
interacción con el resto de la comunidad de estudiantes involucrados en este tipo de certámenes, tanto en el rol de estudiante como de entrenador.

Se realizó un análisis de las diferentes competencias intentando captar sus aspectos característicos, las particularidades que distinguen a cada una 
de ellas y los puntos importantes a tener en cuenta a la hora de prepararse para participar. 

Basándonos en nuestra experiencia personal, intentamos exponer los recursos que nos resultaron útiles para expandir nuestra base teórica,
mejorar habilidades de resolución de problemas y lograr fortalecer los vínculos con otros participantes.

Intentando mostrar de manera concisa y amena las ideas utilizadas para resolver problemas, realizamos una búsqueda por un extenso archivo de enunciados, 
seleccionando problemas que combinen varios conceptos algorítmicos para su resolución y cuyo nivel de dificultad sea asequible para una persona que
se esté iniciando.

Se consultaron publicaciones concernientes a la dinámica de equipo que tiene lugar en entornos de competencia como la ACM ICPC, realizando una exposición
y una crítica sobre las ideas propuestas al respecto.

Mediante una revisión del código fuente implementado en nuestro trabajo de preparación previo a competencias y el código de otros participantes, 
extrajimos técnicas útiles para implementar algoritmos de manera más cómoda y concisa. También se consultó el material de referencia online
de la librería {\em STL} de C++ \cite{stlref} para mostrar algunas de sus herramientas más útiles.

Por último, se recopiló material digitalizado de competencias reales para ilustrar el formato y tipo de problemas ofrecido en cada una de ellas.

\section{Objetivos}

Nos planteamos como objetivo de este trabajo ofrecer al lector un panorama sobre las diferentes competencias de algoritmos.
Estas competencias han crecido mucho en popularidad en diversos países últimamente. Sin embargo, los estudiantes argentinos no han alcanzado 
tal nivel de entusiasmo y estimamos que se debe al desconocimiento sobre los contenidos de estas competencias y a la poca difusión que existe 
en algunas instituciones educativas. Por esto, nos proponemos desmitificar este tema haciendo una exposición clara sobre las modalidades de 
competición y las habilidades teóricas y prácticas que se esperan de los alumnos.
\newline

La resolución de problemas e implementación de soluciones es parte fundamental de la preparación para participar en este tipo de competencias. 
Por ello tenemos como meta facilitar la búsqueda de recursos que permitan al interesado reforzar su background teórico y al mismo tiempo aplicar 
estos conocimientos en la práctica. Brindaremos un variado listado de fuentes para consultar que incluye bibliografía y sitios web con explicaciones 
teóricas, foros y listas de correo donde se pueden encontrar discusiones de problemas e información sobre nuevas competencias, sitios web que organizan 
periódicamente competencias online, jurados online que ofrecen corrección automatizada de programas en un contexto realista.
\newline

Por último, buscamos fomentar el desarrollo de habilidades algorítmicas en el lector. Para esto brindaremos ejemplos de problemas de competencias
anteriores con su correspondiente explicación de las ideas claves para su resolución.

\section{Estructura}

En el capítulo 2 se exponen los aspectos generales y particulares de las 5 competencias estudiadas: ACM ICPC, IOI, Topcoder, Google Code Jam, Codeforces.

El capítulo 3 brinda un completo listado de fuentes útiles para un adecuado entrenamiento que incluye: libros, sitios web, jurados online y redes de
contacto con otros participantes.

En el capítulo 4 se realiza un estudio de técnicas aplicables para coordinar las tareas de un equipo de ACM ICPC tomando como base un trabajo publicado
sobre el tema.

El capítulo 5 intenta mostrar, mediante una serie de ejemplos, ideas interesantes para resolver problemas de naturaleza algorítmica.

El capítulo 6 compila técnicas útiles para implementar algoritmos de manera clara y veloz que son raramente vistas fuera del ambiente de competencias.

Al final del trabajo se incluye un apéndice de enunciados de cada una de las competencias consideradas, el objetivo es dar al lector una idea más precisa
de cómo son presentados los problemas en una competencia real.

\chapter{Competencias}
\section{Introducción}

En este capítulo intentaremos dar un panorama general de las diferentes competencias en las que hemos participado, buscando que el lector logre adquirir 
una noción más concreta de las modalidades y contenidos que puede llegar a encontrar.

En primer lugar, describiremos aspectos comunes a todas ellas. Luego nos concentraremos en las particularidades de cada competencia. Por último, 
presentaremos un análisis comparativo mediante un cuadro que muestre de forma concisa las principales diferencias en base a los siguientes ejes: duración 
de la prueba, sistema de puntajes para cada problema, lenguajes de programación utilizados, modalidad de competencia, tipos de tareas que pueden hallarse 
en una prueba, premios e incentivos, entidad organizadora, a quién representa cada participante (país, universidad, etc.) y si la participación se realiza 
de manera online o presencial.

\section{Descripción general}
                  
Siguiendo nuestro objetivo de desmitificar el contenido de este tipo de competencias vamos primero a refutar ciertas ideas que los estudiantes forman a 
priori sobre qué se exige a los participantes.
\newline

No es necesario tener conocimientos sobre las últimas tecnologías de programación, ni se requiere excelencia en el diseño, código o documentación. 
El eje de las competencias es la resolución de problemas e implementación de algoritmos eficientes. De hecho, el jurado no evalúa el código fuente sino 
que se limita a compilar y testear el programa de manera automatizada. Los fuentes solo se inspeccionan durante la competencia con el fin de chequear que 
no existan errores en el proceso de evaluación.
\newline

Nunca se exige programar una interfaz gráfica, la entrada y salida se realiza a través de archivos de texto, mediante la entrada y salida estándar, o en algunos casos se transmiten datos utilizando parámetros en llamadas a funciones.
\newline

Es muy importante contar con habilidades en resolución de problemas. No se trata de ser eficiente resolviendo ejercicios con un formato bien conocido sino que, generalmente, los problemas planteados requieren de una cierta dosis de ingenio y pensamiento innovador para alcanzar una solución. Por esta razón, el mero estudio teórico de algoritmia no es suficiente. El alumno deberá enfocar gran parte de sus esfuerzos en pensar y resolver problemas de competencias pasadas para adquirir una intuición de los razonamientos necesarios para acercarse a una solución.
Un cierto background matemático suele ser útil para modelar y resolver algunos problemas. Son especialmente importantes la matemática combinatoria, un manejo razonable del álgebra y nociones de probabilidad.
\newline

Los problemas son de naturaleza fundamentalmente algorítmica. Algunos tópicos sobre los que es conveniente poseer conocimientos son:                  
\begin{itemize}
\item Diseño de algoritmos golosos (greedy)
\item Técnica de dividir y conquistar
\item Programación dinámica
\item Teoría de grafos
\item String Matching
\item Búsqueda exhaustiva con pruning
\item Estrategias en juegos adversarios
\item Geometría computacional
\end{itemize}


El objetivo debería ser dominar estos temas en la práctica, conocer cuándo es útil cada técnica, cómo pueden combinarse, y cómo pueden implementarse de manera 
simple y sin errores. La parte teórica queda en un segundo plano ya que el jurado no exige demostraciones formales de la correctitud de las soluciones, 
simplemente deben superarse los casos de test preparados.
\newline

En futuros capítulos, haremos una exposición de estos temas con ejemplos de problemas y soluciones de manera de poder brindar una base a aquel que desee 
iniciar un entrenamiento de sus aptitudes algorítmicas.
\newline

No debe dejar de considerarse la capacidad de realizar un análisis de complejidad básico del tiempo y espacio que insumen los algoritmos diseñados. 
Si bien esta tarea no necesita realizarse de manera demasiado rigurosa, resulta crucial hacer un estimativo del crecimiento asintótico que debería tener una 
solución aceptable. Muchas veces resulta fácil encontrar un algoritmo simple que resuelva correctamente el problema pero, dadas las limitaciones de tiempo y 
memoria, es necesario lograr una solución más eficiente para que ésta sea aceptada.

Al final de los enunciados siempre se especifica cuáles son las restricciones sobre los parámetros de entrada. Esto es lo primero que debe considerarse luego 
de haber entendido el problema.
Por ejemplo, si nos enfrentamos a un problema cuya entrada es una cadena de $n$ caracteres con $n \le 100000$ es razonable buscar una solución en tiempo 
$O(n)$ ó $O(n \log n)$ pero es esperable que un tiempo en $O(n^2)$ sea demasiado.

En general, el énfasis esta puesto en el diseño de un algoritmo eficiente y \emph{NO} en generar un código extremadamente optimizado. 
La eficiencia de las estructuras de datos implementadas en las librerías estándar suele ser suficiente y no es necesario apelar a \emph{hacks} de bajo nivel. 
Los tamaños de las entradas y los límites de tiempo suelen ser cuidadosamente seleccionados de manera de aceptar todas las soluciones asintóticamente adecuadas 
y rechazar aquellos programas con un orden de tiempo de ejecución demasiado grande aún cuando hayan sido ultra optimizados. 
En resumen, hay que concentrarse en el orden asintótico y no tanto en las constantes.
\newline 

En cuanto a la tarea de implementación, es deseable que el programador adquiera una cierta velocidad para codificar y, más importante aún, que lo haga con 
pocos errores. Eliminar errores de un código mal escrito puede ocasionar un retraso muy superior al tiempo requerido para escribirlo.
El testeo es una fase que puede ser de vital importancia, especialmente en las competencias en las que no se otorga puntaje parcial y fallar en un solo caso 
es equivalente a no haber resuelto el problema. Debe prestarse especial atención a los casos borde y poseer la habilidad para construir casos de prueba 
difíciles para testear el programa.
\newline 

Para dar una idea de qué formato presentan los enunciados en cada una de las competencias elegimos presentar un ejemplo muy sencillo de problema al que 
llamaremos \emph{A+B}. El problema simplemente pide sumar 2 números y el objetivo es ilustrar de qué manera se estructuran los enunciados en cada competencia. 

\section{Aspectos particulares}
     
\subsection{ACM International Collegiate Programming Contest}

Esta competencia es una de las más prestigiosas a nivel universitario y es donde los autores de este trabajo han cosechado mayor experiencia.
Una de sus características salientes es que es una competencia por equipos. Cada equipo está compuesto por 3 participantes y tiene a su disposición 1 computadora, 3 juegos de enunciados y útiles para realizar bosquejos y anotaciones. Se permite además llevar material impreso, que generalmente consiste en implementaciones de los algoritmos más importantes.
El hecho de tener una sola máquina para los 3 integrantes hace que, a diferencia de otras competencias, la coordinación de tareas del equipo sea un aspecto a tener en cuenta. Más adelante dedicaremos un capítulo a este tema.

La prueba tiene una duración de 5 horas y consiste en un set de problemas que generalmente son entre 8 y 11. Para su resolución es necesario desarrollar programas de tipo batch que a partir de datos de entrada dados en un archivo o a través de la entrada estándar respondan en otro archivo o la salida estándar la respuesta correcta. El enunciado brinda una descripción precisa del problema así como también el formato exacto que deben respetar los datos de entrada y salida.
Durante la prueba el equipo envía código fuente al jurado, en los servidores se compilan y ejecutan los programas contra una batería de casos de tests y se devuelve un resultado al equipo. Existen 7 resultados posibles:


\begin{itemize}
\item AC: Accepted. Solo se retorna este resultado cuando el programa retorna la respuesta correcta en TODOS los test,  respetando los límites de tiempo y memoria y el formato requerido.
\item PE: Presentation Error. Indica que, esencialmente, el programa retorna la respuesta correcta en todos los casos pero existe algún problema con el formato de la salida, generalmente se debe a espacios o saltos de línea excedentes o faltantes. A los efectos del puntaje final, se contabiliza como un envío incorrecto.
\item WA: Wrong Answer. Nuestro programa termina en tiempo pero da un resultado incorrecto en algún test.
\item TLE: Time Limit Exceeded. El programa no termina de resolver todos los casos bajo el límite de tiempo establecido.
\item MLE: Memory Limit Exceeded. El programa consume más memoria que la permitida.
\item RTE: Runtime Error. Se produjo una terminación anormal del programa. Puede deberse a exceder la capacidad de la memoria stack, indexar a un arreglo fuera de sus límites, intentar acceder a recursos no disponibles (e.g: red, archivos no permitidos), no capturar cualquier tipo de excepción disparada.
\item CE: Compile Error. El código fuente enviado tiene errores sintácticos y no puede ser compilado.
\end{itemize}


La clasificación final de los equipos se realiza considerando en primer lugar la cantidad de problemas resueltos y luego, en caso de empate, la penalidad recibida.
La penalidad se calcula como la suma de las penalidades de los problemas resueltos y la penalidad de un problema será igual a los minutos trascurridos  desde el inicio de la competencia hasta el momento en que se envió la primera solución correcta para dicho problema más 20 minutos por cada envío incorrecto que se haya enviado previamente.  
Por ejemplo, si los envíos fueron:

\begin{fullindent}{\parindent}
21' - WA (Wrong Answer) \\
54' - PE (Presentation Error) \\
59' - AC (Accepted) \\
72' - TLE (Time Limit Exceeded) \\
99' - AC (Accepted)
\end{fullindent}

La penalidad será $59 + 2 \times 20 = 99$
Como puede apreciarse cada envío previo a la primera solución correcta penaliza con 20 minutos, los envíos posteriores no inciden en el cálculo.

Hay varias cosas para analizar aquí. Hay que tener en cuenta que el principal criterio para la clasificación es la cantidad de problemas resueltos, 
por lo tanto intentar minimizar la penalidad recibida es importante pero debe ser considerado un objetivo secundario. 
Cuando se resuelve un nuevo problema la penalidad aumenta (dado que solo los problemas resueltos suman a la penalidad total), de todas maneras siempre es 
conveniente tener una mayor cantidad de problemas resueltos.
\newline

Si bien los problemas de una prueba suelen ser de dificultad muy variada, no se les asigna diferentes puntajes como ocurre en otras competencias. Adicionalmente, el sistema de penalidades toma en cuenta los minutos que transcurrieron desde el inicio hasta que se resolvió cada problema. Por estas razones, se ve claramente que el equipo debería intentar resolver los problemas en orden de dificultad creciente.
El reconocer rápidamente cuáles son los problemas más simples de resolver e implementar es una tarea que requiere coordinación y buena comunicación entre los integrantes del equipo.
Durante la competencia, el equipo tiene acceso a un scoreboard en tiempo real que permite observar las posiciones de cada equipo hasta el momento, pero también brinda información sobre qué intentó resolver cada equipo y en cuáles tuvo éxito. Esta es otra herramienta que sirve como indicio sobre la dificultad de cada problema.
\newline

Otro detalle a observar es la condición para aceptar una solución. Para que el jurado considere un problema como resuelto, el programa enviado debe resolver 
todos los casos de test bajo los límites de tiempo y memoria preestablecidos. No existe aquí posibilidad de obtener puntaje parcial como en otras competencias. 
Por esto es importante desarrollar la habilidad de testear los programas, prestando especial atención a los casos borde. 
También debe hallarse una solución cuyo tiempo de ejecución tenga un crecimiento asintótico adecuado para lograr pasar los test de los casos más grandes.

Los lenguajes que se permiten utiliza en ésta competencia son C/C++ y Java. Antiguamente también estaba disponible la opción Pascal/Delphi y aún sigue vigente
en algunas regionales, no es el caso de la regional de Sudamérica.

\newcommand{\textoliteral}[1]{\mbox{``\texttt{#1}''}}


\begin{problema}
\subsection*{A+B}

Se pide leer $2$ enteros $A$ y $B$ por la entrada estándar. Deberá imprimir su suma en la salida estándar.

\subsubsection*{Input}
La entrada contendrá en una única línea 2 enteros A y B separados por un espacio en blanco ($0 < A,B \le 1000$)

\subsubsection*{Output}
La salida deberá contener una única línea con el resultado.

\subsubsection*{Sample Input}
5 3

\subsubsection*{Sample Output}
8
\end{problema}



Con este ejemplo simple podemos ver todas las secciones que suele tener un problema de ICPC.
Al principio se presenta un enunciado que describe de manera precisa el problema.
Luego se detallan las restricciones que cumplen los datos de entrada y su formato exacto.
Luego se explicita que formato deberá respetar la salida.
Por último, se presenta un ejemplo de entrada y su salida correspondiente.
\\

% \noindent
% \emph{International Olympiad in Informatics (IOI)}
% \newline

\subsection{International Olympiad in Informatics (IOI)}

La IOI es la competencia internacional de programación más prestigiosa para estudiantes de nivel secundario. Generalmente, es donde los participantes de este tipo de torneos realizan su primera experiencia. Se organiza anualmente desde el año 1989.
La prueba es de carácter individual, se realiza en 2 días, cada día se le presentan a los estudiantes 3 problemas de naturaleza algorítmica que podrán resolver en el espacio de 5 horas.
Cada país que toma parte de la IOI puede llevar 4 representantes. Para seleccionar a los participantes que formarán parte del equipo nacional en la IOI, los países organizan competencias nacionales y pruebas de selección.
\newline 

En el caso de la Argentina, existe el programa O.I.A. (Olimpíada Informática Argentina) que se encarga de estas tareas.
Los exámenes de OIA se realizan en varias instancias: escolar, interescolar, zonal, regional y nacional; algunas de estas instancias pueden no realizarse 
cuando la cantidad de inscriptos es inferior al cupo.
Los alumnos se dividen en 3 niveles de la siguiente manera:

\begin{itemize}
\item Primer Nivel: alumnos de 1º y 2º año de secundario o equivalente.
\item Segundo Nivel: alumnos de 3º y 4º año de secundario o equivalente.
\item Tercer Nivel: alumnos de 5º y 6º año de secundario o equivalente.
\end{itemize}

En el Certamen Nacional, además de definirse los campeones de cada nivel, se realiza una preselección de candidatos para integrar el equipo que participará en 
la IOI. La selección final se define con un Certamen de Selección aparte.
Los formatos de examen de los certámenes Nacional y de Selección son muy similares al de la IOI. La principal diferencia es que en el Nacional la prueba es de 
un solo día, mientras que la selección se realiza en 2 días al igual que la instancia internacional.
\newline 

En otras competencias se puede utilizar material impreso o previamente programado. Por el contrario, en OIA e IOI la prueba es de carácter presencial y no se 
admiten esta clase de ayudas. Por lo tanto, la habilidad de implementar rápidamente y sin errores estructuras de datos y algoritmos complejos se torna 
fundamental.
\newline 

Un detalle muy característico de la IOI es la posibilidad de obtener puntajes parciales. Los problemas están pensados para que existan diferentes soluciones 
cuya eficiencia varíe significativamente. En el enunciado se explicitan diferentes restricciones que cumplirán los datos de entrada, dejando en claro cuántos 
puntos es posible obtener si se resuelven las instancias de cada tipo. A continuación presentamos un ejemplo para aclarar este punto:

\begin{problema}

\begin{center} 
\section*{A+B} 
\end{center}

En este problema se te pide que sumes 2 números\\

\subsection*{Tu tarea}
Escribe una función sumar(A,B) que tome los siguientes parámetros
A: el primer sumando
B: el segundo sumando

La función debe devolver el valor de la suma A+B

\subsection*{Ejemplos}
\subsubsection*{Ejemplo 1}
A = 2  B = 11

La suma 2 + 11 da como resultado 13. Tu función debería retornar 13.

\subsubsection*{Ejemplo 2}
…...


\subsection*{Subtareas}

\subsubsection*{Subtarea 1 (10 puntos)}
Al menos uno de los dos números, $A$ ó $B$, será $0$.

\subsubsection*{Subtarea 2 (25 puntos)}
$0 \le A,B \le 1000000$

\subsubsection*{Subtarea 3 (65 puntos)}
$-10^{100} \le A,B \le 10^{100}$

\subsection*{Detalles de implementación}

\subsubsection*{Límites}
\begin{itemize}
 \item Limite de tiempo: 1 segundo
 \item Limite de memoria: 256MB
\end{itemize}


\end{problema}

\begin{problema}
 \subsubsection*{Interfaz (API)}

\begin{itemize}
 \item Carpeta de implementación: sum/
 \item El participante debe implementar: {\tt sum.c} ó {\tt sum.cpp} ó {\tt sum.pas}
 \item Interfaz del participante: sum.h o sum.pas
 \item Interfaz del grader: sum.h
 \item Grader de experimentación: grader.c o grader.cpp
 \item Archivos de entrada para el grader para experimentación: grader.in.1, grader.in.2,...
 \item 
    {\bf Nota:} El grader de experimentación lee la entrada con el siguiente formato:
    \begin{itemize}
    \item Línea 1: A B
    \end{itemize}
 \item Salida esperada para las entradas dadas al grader de experimentación: grader.expect.1, grader.expect.2,...
Cada uno de estos archivos debe contener precisamente el texto “Correct.”.
\end{itemize}

\end{problema}


 
Este formato es el presentado en los últimos 2 años (2010 y 2011). A diferencia de ediciones anteriores los datos no se leen y escriben en archivos de texto o 
utilizando la entrada y salida estándar, estas tareas ahora se realizan a través de parámetros de una función que debe implementar el concursante.
En primer lugar se realiza una descripción del problema en la sección de enunciado. Luego se especifica cuáles serán los parámetros de entrada y salida de la 
función a implementar.

Luego se ofrecen varios ejemplos con el detalle de los datos de entrada y la salida esperada con su correspondiente explicación.
La sección subtareas subdivide los casos de test del jurado en diferentes tipos. Para cada tipo se aseguran diferentes restricciones sobre los valores y el 
tamaño de la entrada, allí también se especifica el puntaje asignado a cada subtarea. Este sistema logra una evaluación más escalonada que en otras 
competencias. Aún sin lograr la solución más eficiente, el participante puede optar por atacar un subconjunto de los test cuyo tratamiento sea más sencillo y 
lograr un puntaje parcial.

Por último, la sección sobre detalles de implementación especifica nombres de directorio, archivos y otros detalles para poder interactuar correctamente con 
el entorno de evaluación del jurado.
\newline 

Otra peculiaridad es la existencia de tareas 'interactivas'. En este tipo de problemas, el programa debe interactuar con una librería provista por el jurado. 
Esto permite la posibilidad de incluir problemas que no pueden ser resueltos por un programa batch. Por ejemplo, es posible pedir un programa que compita en 
un juego por turnos contra un jugador virtual programado por el jurado o exigir una solución online (i.e. el programa debe dar respuestas a consultas a medida 
que recibe datos, sin haber leído la totalidad de la entrada).
\newline

Otro tipo de problemas de IOI que difieren de la modalidad batch de ACM ICPC son los de entrada no secreta (non-secret input). Se trata de problemas con una 
menor cantidad de casos de test. Los participantes tienen acceso a estos test durante toda la prueba, y tienen la posibilidad de resolverlos mediante 
diferentes métodos. Es posible llegar a la solución de algunos casos mediante razonamientos formales utilizando lápiz y papel, o haciendo un trabajo combinado
de programación, experimentación y trabajo manual. De este modo, la actividad se vuelve más parecida a lo que realiza un investigador en el mundo real. 
No se desarrollan programas que se vean sometidos a un límite estricto y fijo de tiempo y espacio sino que es posible desarrollar prototipos y actuar 
consecuentemente a los resultados obtenidos, adaptar el programa a la entrada específica, y utilizar la computadora como una herramienta complementaria al 
razonamiento lógico-matemático puro.

Los lenguajes de programación utilizados en la competencia son C/C++ y Pascal.
\\

\subsection{Topcoder}

Topcoder es una empresa estadounidense que organiza concursos de programación desde 2001.
El modelo de negocios de esta empresa va más allá de las competencias de algoritmos, incluye diseño y desarrollo de componentes para terceros, 
venta de licencias de desarrollos realizados en competencias, plataforma para reclutar programadores destacados y concursos de diseño gráfico.
Topcoder ofrece 2 tipos de competencias relevantes a este trabajo: \emph{Algorithm matches} y \emph{Marathon Matches}.
\\

\subtitulo{Algorithm Matches}


Cada 2 semanas se organiza una SRM (Single Round Match) que, como su nombre lo indica, consiste de una sola instancia. Los participantes compiten online y se 
realiza una clasificación final al término de la prueba.
También se organizan anualmente 2 torneos: Topcoder Open (TCO) y Topcoder High School (TCHS). Los torneos se componen de varias rondas clasificatorias online 
(1 clasificación y 5 rondas online en 2011), los que logran superar estas rondas compiten en las semifinales y final de manera presencial.
En 2010 se utilizó el siguiente esquema de rondas: \\


\begin{tabular}{ l | l }
\textbf{Ronda} & \textbf{Clasificados} \\ 
\hline
Clasificación (Qualification Round) 3 rondas & 600 en cada ronda \\
Ronda 1 (Online Round 1) & 850 \\
Ronda 2 (Online Round 2) & 350 \\
Ronda 3 (Online Round 3) & 150 \\ 
Ronda 4 (Online Round 4) & 60 \\ 
Ronda 5 (Online Round 5) & 24 \\ 
Semifinales (2 rondas) y Repechaje (Wildcard Round) & 8 \\ 
Final &  \\ 
\end{tabular}
\\


Hay 3 instancias de clasificación, cada participante puede participar en una o más de las 3 rondas siempre y cuándo no haya logrado clasificar previamente. Luego se realizan las 5 rondas online de las que finalmente se obtienen 24 personas que viajarán para competir en las rondas onsite. En los últimos años las rondas onsite se realizaron en Las Vegas, y los gastos de traslado y alojamiento son afrontados por la empresa organizadora. Éstas consisten de 2 semifinales con 12 participantes en cada una, 3 participantes de cada semifinal avanzan a la ronda final directamente, los puestos del 4 al 7 tendrán otra chance en una ronda de repechaje. En el repechaje, 8 participantes (4 de cada semifinal) compiten por obtener los 2 últimos cupos en la final. Por último, los 8 finalistas compiten por determinar el campeón del torneo.

La interfaz utilizada para participar es la Topcoder Arena, una aplicación Java que puede ser utilizada como aplicación normal de escritorio o ejecutarse dentro de un navegador en forma de applet. El entorno permite realizar múltiples actividades:
\\

Lobbies: Brinda la opción de chatear con los otros participantes logueados en el sistema o con los administradores durante la competencia.

Practice Rooms: Ofrece la posibilidad de acceder a enunciados de todas las competencias anteriores, enviar soluciones a problemas y someterlo a la batería de tests. Es un entorno muy similar al de competencia real.

Active Contest: Este área se utiliza para participar de las competencias. Permite realizar la registración al evento, acceder a los enunciados, testear y enviar soluciones, chequear el status de los otros participantes mediante el scoreboard. La aplicación también nos brinda un editor de código muy básico para implementar soluciones.
\\

Si bien el entorno ofrece un editor de capacidades muy limitadas, su funcionalidad es altamente extendible. Topcoder provee una interfaz para programar plugins en Java e integrarlos a la funcionalidad básica de la Topcoder Arena. De este modo, se puede personalizar el comportamiento de la aplicación. Es posible utilizar un plugin que extienda la funcionalidad del editor. Otro tipo de plugin muy común, se encarga de tomar ciertos parámetros especificados en el enunciado, generar un “esqueleto” de código en un archivo de texto y a la hora de enviar la solución importar el contenido del archivo. De esta manera, podemos utilizar nuestro entorno de programación preferido para editar código y dejar que el plugin se encargue de integrarlo al ambiente de la competencia.
Existe otra extensión que mejora la función del anterior.  Además de generar un “esqueleto” en un archivo de texto también genera automáticamente código para testear la solución con los ejemplos que se detallan en el enunciado.

El formato de la competencia es el mismo para las SRMs y las rondas de TCO y TCHS.
Se inicia con una fase de programación (coding phase) en donde se presentan 3 problemas y se dispone de 75 minutos para su resolución. Los problemas están ordenados por dificultad y cada uno tiene un puntaje diferente. Los puntajes más comunes son 250 para el fácil, 500 para el medio y 1000 para el difícil. En algunos ocasiones, el puntaje se ajusta para reflejar que la dificultad varía un poco de la media. Por ejemplo, si el problema más difícil de la prueba es más sencillo que lo normal en otras rondas, puede valer 900 puntos.

El participante debe decidir cuándo y en qué orden acceder al enunciado de cada problema a través de la Arena. Esto es relevante ya que el puntaje de cada problema empieza a disminuir en el momento en que se accede a su enunciado. Esto quiere decir que el puntaje se calcula a partir del puntaje inicial y el tiempo transcurrido entre que se lee el enunciado y se envía el problema, a diferencia de otras competencias en los que baja desde el inicio de la prueba.

Luego de un intervalo de 5 minutos, comienza una segunda etapa de debugueo (challenge phase).
Aquí se tiene acceso al código de otros participantes y se pueden realizar challenges. Un challenge consiste en ingresar un caso de test para el código de algún participante esperando encontrar una falla en su solución. En caso de que el challenge sea exitoso se obtienen 50 puntos extras, si el programa responde correctamente al caso planteado se pierden 25 puntos.

Finalmente, luego de la etapa de challenges se realizan la fase de testing. Allí las soluciones son sometidas a la batería de test preparada para cada problema a la que se agregan los challenge exitosos efectuados en la ronda anterior. De esta manera, se aprovecha el ingenio de los participantes que fabricaron casos de test difíciles para lograr un testeo más eficaz.

Los lenguajes utilizables en cada ronda son Java, C++, C\# y VB.NET.

\begin{problema}

\subsubsection*{Problem Statement}

\begin{fullindent}{3ex}


Queremos calcular la suma de 2 enteros.

Dados los enteros {\bf A} y {\bf B} su método deberá devolver la suma de estos números. 
\end{fullindent}





\subsubsection*{Definition}

\begin{fullindent}{3ex}

Class:    APlusB

Method:    sum

Parameters: int, int

Returns: int

Method signature: int sum(int A, int B)

(be sure your method is public)

\end{fullindent}


\subsubsection*{Constraints}

\begin{fullindent}{3ex}
- A se encontrará entre 1 y 1000, inclusive.

- B se encontrará entre 1 y 1000, inclusive.
\end{fullindent}

\subsubsection*{Examples}


0)     
\begin{fullindent}{3ex}

0

15

Returns: 15

La suma de 0 y 15 es 15.

\end{fullindent}

1)     
\begin{fullindent}{3ex}
6

6

Returns: 12

2 veces 6 es 12.
\end{fullindent}
\end{problema}

\begin{problema}
2)     
\begin{fullindent}{3ex}
3

5

Returns: 8

\end{fullindent}

3)     
\begin{fullindent}{3ex}
351

124

Returns: 475
\end{fullindent}

\end{problema}

Todo problema de SRM o torneo en Topcoder respeta este formato.
Primero, se describe el problema en la sección Problem Statement. Cada mención que se hace en el enunciado a un parámetro que se recibirá como entrada se 
remarca en negrita.
Luego, en la sección Definition, se específica el nombre de la clase y el método dentro de esa clase que servirán como interfaz entre el programa de testeo 
del jurado y la solución. En esta competencia, no es necesario efectuar operaciones de entrada y salida, los datos se obtienen a través de los parámetros del 
método definido.
Luego, la sección Constraints especifica todos las restricciones sobre los datos de entrada.
Por último se da una serie de ejemplos, esta suele ser mucho más completa que en otras competencias como ICPC o IOI. 
La cantidad de casos de ejemplo es generalmente mayor a certámenes similares y en muchas ocasiones existe una pequeña explicación sobre la salida correcta 
de los primeros ejemplos.
\\




\subtitulo{Marathon Matches}

Los Marathon Matches fueron creados para plantear desafíos algorítmicos que no fueran compatibles con el formato de los Algorithm Matches clásicos.
Tienen una duración mucho más extensa, que puede ser de varias semanas. El sistema de testeo también varía significativamente, aquí no se chequea 
necesariamente la correctitud de una solución sino que el sistema de puntaje se define de diferente manera para cada problema.

Estas características (duración extensa y scoring específico a cada problema) proveen un marco mucho más flexible para plantear desafíos de variada naturaleza.
En general, se trata de problemas en los que se busca optimizar cierto score y las soluciones pueden involucrar técnicas de data mining, machine learning o 
algún conocimiento técnico específico.
\newline

Algunas grandes empresas se han visto interesadas en proponer problemas y sponsorear estas competencias. NVIDIA lanzó algunos Marathon Match con el nombre 
de `CUDA Superhero Challenge’ en los que se proponía a los participantes resolver un problema usando la tecnología CUDA desarrollada por NVIDIA que permite 
codificar algoritmos para que corran en sus tarjetas gráficas.
La agencia espacial estadounidense NASA, también propuso Marathon Matches en los que ofrecía importantes recompensas económicas a los ganadores por resolver 
problemas concernientes a proyectos de interés para la agencia.
\newline

Los lenguajes con los que se puede trabajar son todos los disponibles para las rondas clásicas de algoritmos a los que se agrega Python.
\\

\subsection{Google Code Jam}


En 2003, Google comenzó a organizar la ya reconocida Google Code Jam con el objetivo de reclutar programadores talentosos.
En un principio, encargó la organización de la competencia a Topcoder, por lo tanto el formato era exactamente el mismo que 
los de la compañía organizadora. La única diferencia notable fue que incluyeron Pyhton como uno de los lenguajes permitidos.

En 2008, Google lanzó su propia plataforma para llevar a cabo las competencias. A partir de aquí, la Google Code Jam adquirió 
características propias y distintivas.

La competencia está estructurada en varias rondas. La primera es una etapa de clasificación (Qualification Round) en donde la 
condición para avanzar es lograr un mínimo establecido de puntos. En las siguientes rondas, se define quiénes avanzan teniendo en 
cuenta la clasificación general. La Ronda 1, esta dividida en 3 subrondas, y los participantes pueden participar en cualquiera de 
ellas, incluso se puede tomar parte en más de una en caso de no haber obtenido la clasificación a la Ronda 2.

Salvo la ronda final, el resto de las instancias son de carácter no presencial, se compite online mediante una interfaz web provista
en el sitio \emph{http://code.google.com/codejam/}.
A continuación presentamos el formato que se siguió en 2011.\\

\begin{tabular}{ p{5cm} | l | p{5cm} }
\textbf{Ronda} & \textbf{Duración} & \textbf{Clasificados} \\ 
\hline
Qualification Round & 24 horas & Todos los que logren el piso de puntos (En 2011, 10336 participantes) \\
Online Round 1A, 1B, 1C & 2h 30m & Mejores 1000 de cada subronda \\
Online Round 2 & 2h 30m & Mejores 500 \\
Online Round 3  & 2h 30m & Mejores 24 \\
Onsite Finals & 4 horas & ------------ \\
\end{tabular}
\newline

Las pruebas generalmente constan de 3 o 4 problemas. En la final, la duración es mayor y puede haber 5 o 6 problemas.

Los problemas de Google Code Jam tienen asignados diferentes puntajes dependiendo de su dificultad. Por lo tanto, ya no es necesario 
identificar y comenzar por los problemas más simples. A veces, puede ser conveniente dedicar más tiempo al problema de mayor puntaje, 
resignando los problemas de menor puntuación. De hecho, en la última final en 2011, el ganador declaró que su estrategia de dedicar más 
de 2 horas al problema más difícil funcionó muy bien. El campeón finalizó la competencia siendo el único en resolver ese problema, lo 
que le dio 60 de sus 90 puntos obtenidos.
\newline

Al igual que en IOI, se brindan diferentes restricciones para un mismo problema otorgando mayor  puntaje a las soluciones cuya eficiencia 
logre resolver las instancias más grandes.

La modalidad de múltiples restricciones en Code Jam sigue un formato fijo. Todos los problemas tienen 2 clases de input: Small Dataset y 
Large Dataset. En el enunciado se especifican claramente los límites y el puntaje que otorga cada dataset.
Se permiten múltiples intentos de resolver el caso pequeño, cada vez que se desee enviar una solución se baja el archivo con los datos de 
entrada y se dispone de 4 minutos para enviar la salida correcta, el sistema responderá si la solución es correcta o no.
En cambio, para el caso grande, solo se puede enviar una respuesta. El resultado de la evaluación solo se obtiene luego de concluida la 
competencia y el tiempo permitido para producir una salida es de 8 minutos.
\newline

Una particularidad muy interesante de esta competencia, es el hecho de que el jurado no compila y ejecuta código para verificar la 
correctitud de los envíos. Durante la competencia se deben bajar los datos de entrada, producir una salida en la propia computadora y 
enviar esta salida al server.

Esto permite una flexibilidad absoluta sobre la elección de herramientas a utilizar para resolver un problema. Por empezar, no existe 
restricción alguna sobre qué lenguaje de programación utilizar, el participante puede elegir su lenguaje preferido por más extraño o 
desconocido que sea. Pero la amplitud de herramientas a disposición va más allá de la elección del lenguaje; incluso es posible resolver 
un problema con planillas de cálculo ó aplicaciones matemáticas.

Si bien el participante obtiene los datos de entrada durante la competencia, esta modalidad difiere considerablemente de los non-secret 
inputs de IOI. En Code Jam, cuando se baja un archivo con el input del problema, se dispara un timer que impone un límite sobre cuanto 
se puede tardar en enviar la salida. Este tiempo es suficiente para que se ejecute un programa previamente realizado, pero no para 
realizar razonamientos sobre la entrada específica y programar algo nuevo que se adapte a ella.

Podemos remarcar que este método, si bien introduce un grado de flexibilidad único, también introduce una pequeña disparidad entre los 
distintos competidores. Aquel que tenga acceso a mejor hardware, tendrá mayor poder de cómputo y una ventaja en cuanto a las constantes 
involucradas en su solución. Como mencionamos previamente, las constantes pocas veces son un factor decisivo para que una solución sea 
aceptada.

\begin{problema}
 
{\large{\bf Problem A.}  A + B}
\\

Small Input: 7 puntos

Large Input: 23 points
\\

{\large Problem}
\\

En esta tarea se le pide que resuelva la suma de 2 números enteros {\bf A} y {\bf B}.
\\

{\large Input}
\\

En la primera línea de entrada se especifica el número de casos a resolver T.

Seguidamente encontrará T casos de test.

Cada caso de test consiste en una única línea donde se especifican 2 enteros separados por un espacio en blanco: A y B.
\\

{\large Output}
\\

Para cada caso de test, escriba una línea de salida conteniendo ``Case \#x: y'', donde x es el número del caso (empezando desde 1) y en donde y representa a suma pedida.
\\

{\large Limits}
\\

$1 \le T \le 100$
\\

{\large Small dataset}
\\
$0 \le A,B \le 1000$
\\

{\large Large dataset}
\\

$0 \le A,B \le 10100$
\\

{\large Sample}
\\


\begin{tabular}{ l  l }
 Entrada & Salida \\
1 1 & Case \#1: 2\\
10 5 & Case \#2: 15\\
53 2 & Case \#3: 55
\end{tabular}

% 1 1
% 
% 10 5
% 
% 53 2
% 
% Salida
% 
% 2
% 
% 15
% 
% 55
\end{problema}


Inmediatamente a continuación del título se detallan los puntajes de los 2 datasets (small y large).
Luego, en la sección Problem, se presenta el enunciado del problema. Después se describe el formato preciso que tendrán la entrada y la salida esperada. La salida siempre tiene el mismo formato: “Case \#x” para indicar el número de caso que se está resolviendo seguido de una o varías líneas que representan el resultado correspondiente.
En la sección Limits se detallan las restricciones sobre los datos de entrada, primero se marcan los límites que serán validos para los 2 datasets y a continuación se mencionan los límites específicos del caso Small y el Large.
Por último, se brinda un ejemplo de archivo de entrada posible con varios casos y cuál sería la salida correspondiente.
\\

\subsection{Codeforces}

Codeforces es una plataforma de competencias de algoritmos lanzada a inicios de 2010 por gente de la Saratov State University de Rusia. 
Se autodefine como "La única plataforma de competencias de programación de la Web 2.0". Es la más nueva entre las competencias de programación que han 
logrado gran cantidad de adeptos alrededor del mundo. Combina varias características de otras competencias que ya hemos mencionado: ACM ICPC, TopCoder, 
Google Code Jam.

De manera similar a Google Code Jam, se participa a través de una interfaz web que provee su sitio: http://codeforces.com/
Las pruebas tienen una duración de 2 horas y presentan 5 problemas de variada dificultad.
\newline 

Se ofrecen 2 formatos de prueba diferentes.
El primer formato ofrecido se basó en la competencia de ACM. Con la sola diferencia de la duración de la prueba y la cantidad de problemas, el resto de las
reglas no difieren significativamente de las de ACM ICPC. La clasificación general se resuelve por cantidad de problemas resueltos, y en caso de empate por
penalidad. La penalidad se calcula exactamente igual a la otra competencia.

Podemos marca como una diferencia, el hecho de que los problemas siempre están ordenados por dificultad creciente, lo cuál evita la tarea de encontrar cuáles 
son los problemas más sencillos.
\newline 

El formato propio de Codeforces, muestra algunas características similares a TopCoder y a IOI.
El sistema de puntajes es muy parecido al de TopCoder. Aquí cada problema tiene diferente puntaje según su dificultad, y a medida que pasa el tiempo su valor 
va disminuyendo. Inicialmente los puntajes de los problemas son de 500, 1000, 1500, 2000 y 2500 y disminuyen un 0,4\% de su valor por cada minuto transcurrido.
A diferencia de Topcoder, todos los enunciados están disponibles desde y a todos los problemas se les comienza a restar puntaje desde el inicio de la prueba.
\newline

Al enviar una solución, el jurado se encarga de realizar un pretest que consiste en compilar y someter el programa a una batería de test muy acotada. Esto 
sirve para evitar errores triviales como enviar un archivo incorrecto que no contiene el fuente deseado, leer los datos de entrada del lugar incorrecto, o 
tener errores de compilación no detectados en el ambiente local pero sí en el compilador del jurado. El pasar el pretest no nos asegura en ningún caso que
la solución sea correcta. En este sentido, el pretest es un mecanismo similar al utilizado en IOI.

El competidor tiene la opción de mandar una nueva solución al problema (resubmit), incluso ya habiendo superado el pretest. 
Esto puede ser útil cuando se descubre un error en la solución enviada y se desea corregirlo.
\newline 

También se implementa una opción llamada hacks similar a los challenges de TopCoder. Luego de pasar el pretest, el participante tendrá la opción de bloquear
(\emph{lock}) el problema en cualquier momento que lo desee. Esto le impedirá enviar nuevas soluciones para dicho problema, pero le permitirá visualizar las
soluciones enviadas por otros participantes y hacer intentos de hacks. Un hack es un caso de prueba que intenta encontrar un error en la solución de otro 
participante. Cada hack exitoso otorga 100 puntos y un hack fallido resta 50 puntos.
\newline

En 2011, la empresa Yandex, motor de búsquedas líder en el mercado ruso, se unió como socio a Codeforces para organizar una competencia con el objetivo de 
reclutar programadores. De manera similar a la Google Code Jam, los participantes compitieron en varias rondas online y los finalistas viajaron a la sede en
Rusia con los gastos cubiertos por la empresa organizadora
\newline

Una característica interesante de esta competencia es la extensa lista de lenguajes soportados.
A septiembre de 2011 son 12 en total: GNU C++ 4, GNU C 4, MS VS C++ 2005, Free Pascal 2, Delphi 7, C\# Mono 2.6, Java 6, Ruby 1.9, Python 2.6, PHP 5.2, Haskell GHC 6.12 y F\# 2.0.

\begin{problema}
 
\begin{center}
{\Large A. A + B}

time limit per test: 5 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output
\end{center}

En esta tarea se le pide que resuelva la suma de 2 números enteros.

\subsubsection*{Input}
La entrada consiste en una única línea donde se especifican 2 enteros separados por un espacio en blanco a y b.

\subsubsection*{Output}
Imprime el resultado de la suma a+b.

\subsubsection*{Sample test(s)}
\begin{fullindent}{2ex}

\begin{xtabular}{ | l |}
input\\
10 5\\
output\\
15\\
\end{xtabular}
\medskip

\begin{xtabular}{ | l | }
input\\
53 2\\
output\\
55\\
\end{xtabular}
\end{fullindent}

\subsubsection*{Note}
En el primer ejemplo, el resultado de sumar 10 y 5 es 15.

\end{problema}

Este es el formato seguido por los problemas de Codeforces.
El encabezado contiene el título junto con los límites de tiempo y memoria establecidos y la especificación del lugar en el que programa deberá leer la entrada e imprimir la salida.
Luego se expone el enunciado del problema, los formatos de la entrada y la salida, casos de ejemplo. Por último, la sección Notes puede tener una explicación bastante detallada sobre alguno de los ejemplos.
\\

\section{Análisis comparativo}


\subsection*{ACM ICPC}
\rowcolors{0}{light-gray}{white}
  \begin{tabular}{ | l | p{6.5cm} | }
  \hline
    Duración & 5 horas \\
    Puntaje & 1 punto por problema. Desempate según penalidad. \\
    Lenguajes &  C/C++, Java \\
    Modalidad de competencia &  Grupal, 3 personas \\
    Tipo de tareas & Tipo batch \\
    Premios - Incentivos & Importantes premios económicos para los campeones mundiales y regionales, y el primer equipo en resolver cada uno de los problemas. \\
    Organizador &  ACM. Patrocina IBM. \\
    Representación & Universidad \\
    Online / Presencial & Presencial \\
  \hline
  \end{tabular}
\newline

\subsection*{IOI}
\rowcolors{0}{light-gray}{white}
  \begin{tabular}{ | l | p{6.5cm} | }
  \hline
    Duración & 5 horas \\ 
    Puntaje & 100 puntos por problema. Puntajes parciales. \\ 
    Lenguajes &  C/C++, Pascal \\ 
    Modalidad de competencia &  Individual \\
    Tipo de tareas & Tipo batch. Tareas interactivas. Entrada no-secreta. \\
    Premios - Incentivos & Medallas honoríficas. \\
    Organizador & Comité organizador de la IOI \\
    Representación & Nacional \\
    Online / Presencial & Presencial \\
  \hline
  \end{tabular} 
\newline

\subsection*{Topcoder}
\rowcolors{0}{light-gray}{white}
  \begin{tabular}{ | l | p{6.5cm} | }
  \hline
    Duración & Coding: 75 minutos. Challenge: 15 minutos \\ 
    Puntaje & Puntaje variable según dificultad (generalmente 250, 500 y 1000 puntos). Disminuye a medida que pasa el tiempo\\ 
    Lenguajes &  Java, C++, C\#, VB.NET \\ 
    Modalidad de competencia & Individual \\
    Tipo de tareas & Tipo batch \\
    Premios - Incentivos & Incentivos económicos. Viajes\\
    Organizador & TopCoder Inc.\\
    Representación & Personal \\
    Online / Presencial & Online. Finales de torneos presenciales \\
  \hline
  \end{tabular} \\


\subsection*{Google Code Jam}
\rowcolors{0}{light-gray}{white}
  \begin{tabular}{ | l | p{6.5cm} | }
  \hline
    Duración & Qualy: 24 horas. Rondas Online: 2hs 30m. Ronda Final: 4hs. \\ 
    Puntaje & Puntaje variable según dificultad. 2 tamaños de entrada por problema con diferentes puntajes. Desempate según penalidad.\\ 
    Lenguajes & Sin restricciones  \\ 
    Modalidad de competencia & Individual \\
    Tipo de tareas & Tipo batch\\
    Premios - Incentivos & Incentivos económicos. Viajes. Oportunidad laboral.\\
    Organizador & Google\\
    Representación &  Personal\\
    Online / Presencial & Online. Finales presenciales \\
  \hline
  \end{tabular} \\


\subsection*{Codeforces}
\rowcolors{0}{light-gray}{white}
  \begin{tabular}{ | l | p{6.5cm} | }
  \hline
    Duración & 2 horas \\ 
    Puntaje & Puntaje variable por problema (500, 1000, 1500, 2000 y 25000). Disminuye a medida que pasa el tiempo.\\ 
    Lenguajes & GNU C++ 4, GNU C 4, MS VS C++ 2005, Free Pascal 2, Delphi 7, C\# Mono 2.6, Java 6, Ruby 1.9, Python 2.6, PHP 5.2, Haskell GHC 6.12 y F\# 2.0. \\ 
    Modalidad de competencia & Individual \\
    Tipo de tareas & Tipo batch \\
    Premios - Incentivos & Placer de competir. Viajes y oportunidad laboral (Yandex).\\
    Organizador & Saratov State University (Rusia).\\
    Representación & Personal \\
    Online / Presencial & Online. Las finales de Yandex son presenciales. \\
  \hline
  \end{tabular} \\

\rowcolors{0}{white}{white}

\chapter{Entrenamiento}

\begin{flushright}
% \begin{quote}
``La práctica hace a la perfección" \\
Saber popular
% \end{quote} 
\end{flushright}




Frase trillada pero siempre vigente.
No hay grandes secretos sobre cómo lograr el éxito. Más allá de las habilidades innatas de los participantes, motivación, formación académica o 
cualquier aspecto que queramos analizar, no hay ningún secreto escondido, para intentar alcanzar el objetivo propuesto todos debemos atravesar el mismo camino: 
la práctica.

Afortunadamente, existen numerosos recursos con los que contamos para mejorar nuestro desempeño en competencias.

\section{¿Cómo entrenar?}

La clave del entrenamiento es desarrollar la habilidad de resolver problemas. Para esto, no hay modo más eficaz que enfrentarse a problemas de competencias pasadas e invertir un tiempo considerable tratando de llegar a una solución. No siempre se logra resolver el problema, en estos casos es posible acudir a la solución. De todas maneras, el esfuerzo realizado no será en vano ya que el solo ejercicio de intentar lograr una solución desarrollará nuestra intuición para enfrentar nuevos ejercicios y habremos logrado un entendimiento más profundo del problema.
Es importante seleccionar problemas de una dificultad que se corresponda con nuestra habilidad de resolución. Es aconsejable dejar los problemas más complejos para las etapas de entrenamiento más avanzadas en las que nuestro nivel nos permita una mayor chance de resolverlos. Por otro lado, con los problemas demasiado sencillos no lograremos desarrollar nuevas habilidades.
Este ciclo de leer un problema, pensarlo y resolverlo o leer su solución hará que nuestro nivel vaya incrementándose gradualmente y nos permitirá abordar problemas cada vez más complejos.

Si bien existen problemas en los que una base teórica es necesaria para poder atacarlos, la teoría cumple un rol secundario en este proceso de entrenamiento. El enfoque central debería apuntar a la práctica de resolución de problemas, acudiendo a la teoría cuando signifique una limitación para seguir avanzando.
Existe una amplia variedad de libros con un excelente contenido teórico que nos servirá como herramienta a la hora de resolver problemas pero es muy importante aclarar que el mero manejo teórico de algoritmos no será suficiente, es necesaria la práctica para desarrollar una fluidez en la utilización, combinación e implementación de estas herramientas.

Existen numerosos sitios webs en los que se pueden encontrar archivos de problemas para ejercitarse. Las páginas de competencias suelen tener una sección para practicar con las problemas utilizados en pruebas anteriores. Adicionalmente, existen sitios llamados Jurados Online (Online Judges) que poseen un vasto archivo de enunciados recolectados de diferentes competencias y que brindan una interfaz para enviar soluciones y someterlas a un testeo automatizado en tiempo real.
Un método extremadamente útil para aprender a implementar algoritmos y estructuras de datos de manera rápida, concisa y libre de errores es leyendo el código de los participantes más experimentados. Esto es posible gracias a que algunos sitios nos permiten acceder al código desarrollado por otros competidores.

Cuando un equipo se entrena para participar en un certamen de ACM ICPC, es importante que logren coordinar las tareas, el manejo del tiempo y la utilización de la máquina. Para esto, lo más efectivo es realizar simulacros intentando reproducir las condiciones reales de competencia tales como cantidad y dificultad de los problemas, duración, uso de una sola máquina, etc. Aquí es donde resulta de mucha utilidad la funcionalidad ofrecida por un Jurado Online.

Para atravesar este proceso de entrenamiento siempre resulta útil contar con una guía. El sitio web de la Usaco provee un plan de entrenamiento que puede ayudarnos a organizar esta tarea.
Sin duda, la presencia de una persona que tenga experiencia en estas competencias es la opción más enriquecedora. Nos puede ayudar seleccionando problemas interesantes y adecuados a nuestro nivel, proveyendo pistas para alcanzar una solución, facilitando material teórico, compartiendo su experiencia persona y sirviendo como apoyo moral.

Debemos tener en cuenta que no somos los únicos en este camino, hay miles de personas como nosotros entrenando, aprendiendo y enseñando en la comunidad algorítmica. La tarea se hace más sencilla cuándo se trabaja en conjunto. Existen diversos canales de comunicación donde se pueden compartir ideas y pedir u ofrecer ayuda tales como listas de correo destinadas a tal fin, foros dentro de los sitios de competencias y Training Camps.

\section{Libros}


% \subsection*{
% Introduction to Algorithms \\
% \normalsize Cormen, Leiserson, Rivest, Stein \\
% \small MIT Press
% }

% \begin{tabular} { l l } 
%   \begin{minipage}{0.5\textwidth}
%     \subsection*{Introduction to Algorithms \\
%     \normalsize Cormen, Leiserson, Rivest, Stein \\
%     \small MIT Press}
%   \end{minipage}
% &  
%   \begin{minipage}{0.5\textwidth}
%     \hspace{2ex}
%     \includegraphics[height=4cm]{./img/libros/1.jpg}
%   \end{minipage}
% \end{tabular}
% \bigskip


\libro
{Introduction to Algorithms}
{Cormen, Leiserson, Rivest, Stein}
{MIT Press}
{./img/cormen.jpg}

Este primer libro que proponemos podría ser denominado como la ``Biblia de los Algoritmos". Se trata de una publicación de MIT Press y está pensado como 
texto de referencia para un curso extensivo de algoritmos a nivel universitario.

Se destaca por la calidad de su redacción y la claridad de sus explicaciones y el listado de tópicos que cubre es muy completo.
Es una excelente opción para iniciarse en la algoritmia para cualquier persona que posea un manejo razonable del paradigma imperativo de programación y 
estructuras de datos básicas. Nos atrevemos a decir que dentro de la comunidad de participantes es el libro más utilizado.

Si tenemos que buscarle algún punto débil, podemos mencionar que el capítulo de String Matching no cubre algunos temas importantes como el algoritmo de 
Aho-Corasick y las estructuras de Suffix Trees y Suffix Arrays.  En cuanto a teoría de grafos, no llega a tratar algunos temas más avanzados como Flujo 
de Costo Mínimo.

\libro
{Algorithms}
{Robert Sedgewick}
{Addison-Wesley}
{./img/sedgewick.jpg}

Este libro constituye una variante al más reconocido Introduction to Algorithms que presentamos previamente. Se trata de un texto que abarca una 
amplia lista de temas de naturaleza algorítmica. Es una buena alternativa para estudiar algoritmos clásicos, especialmente para algunos temas que no 
están del todo cubiertos en el libro anterior entre los que podemos mencionar , biconectividad: puntos de articulación y puentes, suffix arrays, parseo
de lenguajes y expresiones y algunos conceptos de geometría computacional.

\libro
{Concrete Mathematics}
{Graham, Knuth, Patashnik}
{Addison-Wesley}
{./img/concrete.jpg}

En entrevistas realizadas en Topcoder a los ‘programadores estrella‘, varios de ellos mencionan este libro como uno de los más importantes para su 
formación.
Si bien sus capítulos se centran en nociones matemáticas, su enfoque práctico lo convierte en una herramienta muy útil para abordar el análisis y diseño 
de algoritmos.
\newline

La historia del nacimiento del libro es interesante. Donald Knuth, reconocido experto en ciencias de la computación, al escribir su enciclopédica obra 
‘The Art of Computer Programming’ se dio cuenta de era necesario cierto bagaje matemático para un análisis sólido de la programación de computadoras y 
que él nunca lo había aprendido en sus cursos de matemática. Decidió entonces abrir una cátedra en Stanford que enseñara todo lo que hubiera querido que 
le enseñaran. Este libro surge como una referencia detallada de los temas abarcados en dicho curso.

\libro
{The art of computer programming}
{Donald Knuth}
{Addison-Wesley}
{./img/taocp.jpg}


Dentro de la comunidad de las Ciencias de la Computación es considerado como el primer y más completo tratado sobre el tema. Se trata de una obra 
faraónica que emprendió el autor a partir del año 1962 y cuya terminación está estimada para 2020.
La obra está pensada en 7 extensos volúmenes que abarcan minuciosamente cada tema tratado.
No es un libro fácil de leer dado el extremado nivel de detalle y profundidad alcanzado en cada tópico y, principalmente, porque las implementaciones 
de los algoritmos están hechas en un lenguaje assembler para una máquina hipotética (MIX) creada por Knuth.

\begin{flushright}
``If you think you're a really good programmer...

read (Knuth's) Art of Computer Programming...

You should definitely send me a résumé if you  

can read the whole thing."

{\em Bill Gates}
\end{flushright}

La frase de Bill Gates deja en claro que este libro no está destinado a ser leído en su completitud por cualquier estudiante promedio con un poco de 
voluntad. De todas maneras, la lectura de algunos de sus pasajes resultan realmente interesante y puede ser utilizado como referencia para algún tema 
muy específico en el que se desee ahondar.

El principal atractivo que ofrece es la variedad de sus ejercicios de muy diversa dificultad. El autor indica la dificultad de cada ejercicio propuesto mediante 
una escala que va de {\bf 00:} ejercicio trivial a {\bf 50:} problema abierto de investigación.


\section{Sitios Web}

\subsection*{USACO: USA Computing Olympiad\\
\normalsize http://ace.delos.com/usacogate}
% \titulo{}

Es la web de la Olimpíada de Informática de USA para estudiantes secundarios (el equivalente a la OIA de Argentina). Contiene una sección de 
entrenamiento, la cual consiste en una serie de capítulos divididos en secciones. Los capítulos y secciones están ordenadas por dificultad: 
de menor a mayor. Cada sección contiene alternadamente problemas a resolver y teoría.


Para pasar a la siguiente sección, se deben resolver todos los problemas de la sección actual. Al terminar la última sección de un capítulo, se 
comienza automáticamente con el siguiente capítulo. La web de la USACO contiene en total 6 capítulos: Getting Started, Bigger Challenges, Techniques 
more subtle, Advanced algorithms and difficult drills, Serious challenges y Contest Practice.
\newline

Los problemas se corrigen automáticamente por el jurado online. Los lenguajes permitidos son los mismos que los permitidos en la IOI: C/C++ y Pascal.
En los últimos años se agregó también Java. El formato de los problemas es similar al de la IOI (justamente se entrena para eso).

En caso de que el código subido falle, se puede ver en qué caso de prueba falló y cuál era la salida esperada para esa caso de prueba. 
Una vez resuelto el problema, se habilita la opción de ver un análisis detallado del problema y código de ejemplo.

La USACO organiza, además, contests online divididos en 3 categorías según la dificultad: Gold, Silver, Bronze.
\newline

Como principal aspecto positivo de esta web, destacamos que es ideal para el que recién empieza y no sabe bien cómo entrenarse, ya que representa 
una excelente guía de aprendizaje, conteniendo análisis de todos los problemas, teoría complementaria y relevante a los problemas que se están 
resolviendo en el momento. El sitio web de la USACO es, en nuestra opinión, una de las primeras herramientas que toda persona que se está iniciando 
en las competencias de programación debería utilizar. Sin embargo, este modelo tan guiado presenta una desventaja: es imposible saltear un problema 
en caso de que deseemos hacerlo.

Cabe destacar que el análisis de un problema solo se puede ver una vez resuelto el problema. Esto no es bueno en caso de que nos topemos con un 
problema que no logramos resolver. Al subir una solución, se ven los casos de prueba en los que fallamos, lo cual facilita el debugueo, pero a su 
vez puede tentarnos a no asegurarnos de que el código sea correcto desde el principio. Algunos problemas cuentan con pistas (hints) para ayudarnos 
en su resolución.


Curiosidad: El 99\% de los problemas menciona a una o varias vacas.

\subsection*{TopCoder\\
\normalsize http://community.topcoder.com/tc}

Posee una sección de tutoriales creados por los mismos usuarios de la web. Algunos de éstos son bastante generales (estructuras de datos, 
algoritmos sobre grafos, etc) y otros son más específicos (usos de librerías en C++) y suelen contener varios “tricks” muy útiles en competencias 
y que no suelen encontrarse en un tutorial estándar de programación.


Lo mejor que tiene es que se puede acceder a la plataforma online donde se suele competir y acceder a TODOS los problemas de competencias anteriores 
y hacerlos bajo el mismo entorno de competencia. Los problemas figuran divididos en dos categorías por dificultad (que se condicen con las dos 
categorías que existen para las competencias) DIV1 (los más difíciles) y DIV2(los más fáciles).


Durante el testeo del programa solución, se pueden ver todos los casos de prueba testeados, el resultado esperado para cada uno de ellos y el resultado que nuestro programa arrojó.     A su vez, se puede acceder al código creado por todos los participantes anteriormente, tanto los escritos durante las sesiones de competencia como durante la práctica. Esta es una característica muy importante, ya que nos permite aprender directamente de algunos de los mejores programadores del mundo. Podemos entender así cómo alguien puede resolver e implementar en 3 minutos un problema que a nosotros nos llevó 30.
    Adicionalmente, un gran porcentaje de las competencias poseen una sección donde un usuario experimentado realiza un análisis detallado de cada problema y muestra ejemplos de códigos que lo resuelven. Existe también la posibilidad de filtrar los problemas por dificultad, autor, tipo de problema, etc. A pesar de tener un gran volumen y variedad de problemas, Top Coder tiene como desventaja que no posee una guía específica de entrenamiento para principiantes.
    Es interesante resaltar que la mayoría de los problemas, explicaciones y tutoriales son creados por usuarios experimentados del sitio (que generalmente reciben una retribución económica por su trabajo).
  
\subsection*{Google Code Jam\\
\normalsize http://code.google.com/codejam/}

Posee un sistema similar al de TopCoder: se puede acceder y enviar los problemas de todas las competencias anteriores, así como ver el código escrito 
por cada uno de los participantes de esa competencia. A diferencia de TopCoder, no se puede ver el código creado por otros durante la práctica, solo 
el creado durante competencias.


Al ser una competencia anual única, el volumen de problemas que contiene es mucho menor al de otros sitios como TopCoder, Codeforces y demás. 
Sin embargo, la calidad de los problemas supera ampliamente a la de las demás webs.


Dado que se permite cualquier lenguaje de programación, tiene como ventaja que podemos acceder a una variedad muy enriquecedora de códigos creados 
por otros.
\\

\subsection*{Codeforces\\
\normalsize http://codeforces.com/}

Es un sitio web 2.0 sobre competencias de programación. Realizan por lo menos una competencia
semanal, lo cual resulta útil si se quiere mantener un buen ritmo de entrenamiento. 
Cada usuario posee su propio blog, y la página principal muestra posts de blogs de distintos
participantes. Existe, además, un sistema de ranking entre los usuarios, basado en sus logros
obtenidos durante las competencias. 

Codeforces soporta numerosos lenguajes de programación, entre ellos C/C++, Free Pascal, C\#, Java, Ruby, Python, PHP y Haskell.


\subsection*{UVA Online Judge\\
\normalsize http://uva.onlinejudge.org/}

Es un Online Judge creado por la Universidad de Valladolid. Posee un archivo de todos los problemas que aparecieron en las competencias de la 
ACM ICPC, tanto las competencias regionales como las World Finals.
\newline 

Los problemas se encuentran divididos según la competencia en la que se los tomó. Esto es una gran ventaja a la hora de hacer un simulacro de una 
determinada competencia. Por ejemplo, si estamos entrenando para una competencia Regional de ACM ICPC, probablemente nos interese hacer simulacros 
sobre Regionales anteriores correspondientes a la misma región.

La modalidad de corrección de problemas es, obviamente, la misma que se utiliza en las competencias de ACM.


\subsection*{SPOJ (Sphere Online Judge)\\
\normalsize http://www.spoj.pl/}

Fue creado por Sphere Research Labs. Contiene un archivo de enunciados muy grande: más de 6000 problemas actualmente. Salvo algunas excepciones 
para ciertos problemas, se puede utilizar una amplia variedad de lenguajes, tales como:  C, C++, Pascal, JAVA, C\#, Perl, Python, Ruby, Haskell, etc.
\\

\subsection*{Otros Jurados Online}

\begin{itemize}
\item Peking University Judge Online: http://poj.org/
\item Timus Online Judge: http://acm.timus.ru/
\item Codechef: http://www.codechef.com/
\item Fuzhou University Online Judge: http://acm.fzu.edu.cn/
\item Harbin Online Judge: http://acm.hit.edu.cn/
\item Hangzhou Dianzi University: http://acm.hdu.edu.cn/
\item Moscow Online Judge: http://acm.mipt.ru/judge/login.pl?lang=en
\item National Taiwan University Online Judge: http://acm.csie.ntu.edu.tw/ntujudge/index.php
\item Tianjin University Ipeiyang University: http://acm.tju.edu.cn/toj/
\item Wuhan University Online Judge: http://acm.whu.edu.cn/oak/
\item Zhejiang University Online Judge: http://acm.zju.edu.cn/onlinejudge/
\end{itemize}


\section{Redes de apoyo}

Desde hace ya varios años, las principales potencias del mundo en competencias de programación, tales como Rusia, China y Estados Unidos, 
organizan regularmente Training Camps para los participantes de estos certámenes. Los entrenamientos poseen una duración que varía entre 1 y 3 
semanas. Durante este tiempo, los competidores tienen la oportunidad de relacionarse entre sí, facilitando así el intercambio de conocimiento.


Este tipo de entrenamientos suele contar con clases teóricas, práctica de problemas y explicación de soluciones, teniendo un fuerte apoyo de parte 
de ex-participantes.
\newline

En nuestro país se realizó en el año 2010 el primer Training Camp a nivel nacional. El mismo tuvo lugar durante una semana en la Universidad de 
Buenos Aires y concurrieron alrededor de 30 participantes, provenientes de Buenos Aires, Córdoba, Rosario, Bahía Blanca y La Plata. El programa 
consistía de un simulacro de prueba durante la mañana y una discusión de las soluciones durante la tarde. Además, hubo clases teóricas dictadas 
por ex-participantes de competencias de ACM.

En el 2011 se repitió la experiencia bajo la misma modalidad, pero esta vez se contó con presencia internacional: acudieron alumnos de las 
Universidades de Lima y Cuzco (Perú) y de La Paz, Oruro y Santa Cruz de la Sierra (Bolivia). Asistieron en total 40 personas.
Durante el último Training Camp se utilizó un sitio web que permite crear fácilmente una competencia online a partir de un set de problemas dado. 
Esto ayudó en gran manera a la realización de los simulacros diarios. El sitio en cuestión es krasnaia.org.
\newline

A partir de estos encuentros se creó una lista de correo “entrenamiento-acm”, la cual representa un canal de comunicación muy importante entre los 
distintos participantes, ya que permite compartir fácilmente problemas, soluciones, dudas, ideas y sugerencias. Esto es de especial relevancia para 
las personas que viven en lugares donde las competencias de programación no son muy populares, porque les da la oportunidad de generar un intercambio
que de otra manera no sería posible.
\newline

Otro recurso muy útil a la hora de entrenar son los foros. Existen varios foros dedicados en los que se puede contactar a otros participantes para 
pedir ayuda. Uno de los más importantes es el foro de Top Coders (http://apps.topcoder.com/forums/), en donde se puede discutir sobre los problemas 
de las competencias del sitio.


\chapter{Trabajo en equipo}

\section{Aspectos generales}

En entornos de competencias ACM ICPC, el trabajo en equipo y la coordinación de tareas son elementos muy importantes para lograr buenos resultados.

Cada equipo consta de 3 participantes, solo hay una computadora disponible, la prueba dura 5 horas, los problemas tienen dificultades muy variadas y el 
tiempo utilizado en resolver cada problema influye en el resultado final. Hay que ser conscientes de que se dispone de 15 horas hombre y 5 horas máquina,
tener a 2 o 3 personas delante de la máquina o dejar la computadora ociosa demasiado tiempo puede significar un malgasto de recursos. 

Por otro lado, no hay que desestimar el trabajo en equipo, muchas veces se resuelven problemas en conjunto con otras personas que de otra manera no 
hubieran sido resueltos.
\newline

Para empezar, dado que la competencia es por equipos, es necesario identificar las fortalezas y debilidades de cada uno de los miembros. Podemos 
reconocer diferentes habilidades que son útiles durante las competencias: resolución de problemas, programación, testeo, debugueo. Los roles deberán 
determinarse en función del conjunto de habilidades que posea cada persona.
Algunos podrán tomar el rol de programador y estar la mayoría del tiempo delante de la computadora programando, otros pueden dedicar la mayor parte de 
su tiempo leyendo y resolviendo problemas, también es posible que alguien tenga entre sus tareas encontrar errores en los programas que fallan.
Por supuesto, estos roles pueden solaparse, una persona puede tener varios roles y un rol puede ser desempeñado por más de una persona. También es 
necesario que haya un cierto nivel de flexibilidad para que el equipo pueda adaptarse al estilo de prueba al que se está enfrentando en el momento.

Es importante qué cada integrante conozca las fortalezas de sus compañeros, para poder darle rápidamente los problemas que le correspondan
\newline 

Teniendo en cuenta el sistema de penalidades de la competencia, en el que cada problema resuelto suma una penalidad igual a la cantidad de minutos 
transcurridos desde el comienzo de la prueba, es necesario identificar y resolver primero los problemas más sencillos. Para esto, es importante que los 
miembros coordinen el orden en que leerán los problemas y se comuniquen eficientemente para decidir cuál será el próximo problema a resolver. 
Por ejemplo, uno de los participantes podría comenzar desde el primer problema en orden ascendente, otro desde el último en orden descendente, y otro 
desde algún punto intermedio. 

La buena comunicación y conocimiento de los compañeros también es necesaria en ocasiones en las que más de un miembro del equipo trabajen sobre el mismo 
problema.
\newline

En cuanto a la tarea de debugueo existen 2 opciones: en la computadora o en papel. Generalmente, en un entorno de competencia tenemos la opción de mandar
a imprimir el código fuente o cualquier otro archivo de texto. Dada la limitada cantidad de horas máquina disponibles, es muy recomendable utilizar la 
opción de imprimir y debuguear sobre el papel, incluso si nos llevara el doble de tiempo encontrar errores seguiría siendo ventajoso.
\newline

Una mínima documentación centralizada puede ser conveniente para dinamizar las tareas del grupo. Es recomendable llevar un registro de cada problema con 
datos como: estado (no resuelto, resuelto, programado, en debugueo, etc.), nivel de dificultad, algoritmo a utilizar, encargado de programarlo, 
casos de test interesantes, etc.

\section{Trabajos publicados}

Existe un trabajo publicado por un ex-participante de la ACM ICPC sobre estrategias y trabajo en equipo \cite{teamwork}.
Allí analizó las posibles estrategias de equipo, analizando cómo se distribuirían las distintas tareas entre los integrantes y los pros y contras de cada
una de ellas.
\newline

Una de las estrategias propuestas es la de trabajo individual, en la que cada integrante trabaja de manera independiente en un problema.
Luego describe 3 estrategias grupales.

La primera: el método de especialización. Propone que cada integrante sea experto en cierto tipo de problemas y durante la prueba se delegan los 
problemas al especialista de cada área.

Luego expone un método basado en tareas en el que un integrante se encarga de la resolución de problemas, otro de la programación y el tercero realiza 
la función de testeo.

Por último, se describe el método del manager. Aquí se conservan los roles de programador y de encargado de la resolución pero el tercer integrante es un 
manager que realiza la toma de decisiones y coordinación de las tareas del equipo.
\newline

Consideramos que la estrategia individual puede ser aplicada durante parte de la prueba pero no como una estrategia pura en la totalidad de la 
competencia. Es conveniente trabajar individualmente durante la resolución de los problemas más fáciles al inicio de la prueba.
Para poder aplicar esta estrategia es necesario que todos los integrantes sean capaces de resolver e implementar un problema en su totalidad. 
Por ejemplo, no sería posible cuando uno de los integrantes es un matemático y no tiene conocimientos de programación.

En las finales mundiales se puede ver que, incluso los mejores equipos cuyos integrantes están muy capacitados en una amplia gama de habilidades, 
necesitan apelar al trabajo colaborativo para atacar los problemas más complejos.

El hecho de disponer de una sola máquina, implica un cierto grado de comunicación y coordinación de las tareas, al menos en cuanto a la distribución del 
uso de la computadora. Por lo tanto, no concebimos posible un método sin comunicación alguna.
Por último, hay situaciones en las que trabajar paralelamente en diferentes tareas pierde sentido. Por ejemplo, sobre el final de la prueba, cuándo el 
tiempo es muy limitado y es físicamente imposible resolver más de un problema, la única opción razonable es trabajar conjuntamente en un único problema.
\newline

Dentro de las estrategias grupales propuestas, consideramos que el método de especialización puede ser el más adecuado. Suele ser el caso, que cada 
integrante se destaque en diferentes tipos de problemas y sus compañeros conozcan bien sus áreas de especialización. Como contra destacamos que, al igual
que en el método de trabajo individual, sigue siendo necesario que cada integrante pueda resolver un problema y programar la solución sin recibir ayuda 
de sus compañeros. Sería más adecuado que el método no sea tan estricto, es decir que todos los integrantes tengan un manejo básico de cada tema y puedan
ayudar al especialista cuando fuera necesario.
\newline

El método basado en tareas puede funcionar en un equipo que cuente con un programador muy eficiente y otro integrante con una gran capacidad para resolver 
problemas. El rol definido para el debugger resulta ineficiente: dos personas trabajando sobre el mismo problema no es un método aplicable durante toda la 
prueba. Coincidimos con una de las falencias que remarca Amraii: un solo programador trabajando durante las 5 horas de prueba probablemente termine 
exhausto y con dificultad para concentrarse.

Otra desventaja de este método es que asume que se tarda la misma cantidad de tiempo en promedio en resolver un problema que en programarlo. 
Se puede producir un desfasaje entre la resolución y la implementación, en cuyo caso será necesario destinar más esfuerzos a la tarea que se encuentra
atrasada.
\newline

El método del manager, si bien es propuesto como el más eficiente, no nos parece un enfoque acertado.
No creemos necesario reservar un rol específico para efectuar la toma de decisiones, lo puede realizar el miembro más experimentado del equipo 
independientemente de si se encarga de programar, resolver problemas o ambas.

La función asignada al manager de preguntarle al programador sobre cada parte de su código de manera de poder detectar errores, nos parece absolutamente 
ineficiente. Esto puede generar más distracciones y fallas en la comunicación que soluciones.

Esta última estrategia parece fundamentada en principios similares a los de la Ingeniería de Software, las tareas de diseño de solución, programación y 
testeo están bien separadas, el manager cumple una función semejante a la de un team leader de un proyecto de software. Esto resulta conveniente para 
proyectos de desarrollo de grandes aplicaciones. Las competencias de programación tienen características y objetivos muy diferentes a los del desarrollo 
tradicional de software. Conceptos como reusabilidad, mantenibilidad, extensibilidad, modularidad y elegancia no resultan importantes en este tipo de 
certámenes. Los únicos objetivos resultan la correctitud y la eficiencia.
\newline

El trabajo remarca la importancia de realizar un testeo exhaustivo para evitar enviar soluciones con errores. Muchas veces es conveniente enviar el 
programa sin realizar demasiado testeo con el riesgo de obtener un WA (Wrong Answer) apostando a que si la solución era correcta se ahorrará penalidad y 
tiempo para resolver otros problemas. Incluso aunque la solución fuera incorrecta, se logra un testeo inmediato contra los casos preparados por el jurado 
a un costo de 20 minutos de penalidad, lo cual resulta razonable en ciertas circunstancias.

\chapter{Resolución de problemas}

\section{Introducción}

Existen numerosos campos dentro del estudio de algoritmos que resultan útiles a la hora de enfrentarse a un problema de competencia.
Entre algunos de ellos podemos listar los siguientes:

\begin{itemize}
\item Algoritmos Greedy
\item Divide \& conquer
\item Programación dinámica
\item Teoría de grafos: recorridos, conectividad, caminos de costo mínimo, flujo máximo, etc.
\item String Matching
\item Backtracking / Pruning
\item Estrategias en juegos adversarios
\item Geometría computacional
\end{itemize}

Una exposición teórica de cada una de estas técnicas y los algoritmos estándar más frecuentemente utilizados escapan al alcance de este trabajo.
Asimismo, el estudio de un problema real de competencia para cada una de estas categorías junto a una exposición de su solución daría como resultado
un capítulo demasiado extenso y de tediosa lectura.

Por estos motivos y aprovechando el hecho de que las competencias suelen requerir la combinación de diversas técnicas de manera ingeniosa, hemos
decidido realizar una selección reducida de problemas que abarque la mayoría de los temas y permita mostrar cómo se pueden utilizar de manera conjunta
para lograr soluciones.
\newline

La siguiente sección se dedicará a exponer una serie de problemas, presentando en primer lugar el enunciado y luego una explicación de su solución
así como un análisis de la complejidad en cuanto a tiempo de ejecución.

No nos explayaremos en la teoría subyacente a cada solución, brindaremos referencias para que el interesado pueda remitirse a los libros y/o papers 
correspondientes.

\section{Problemas}

%%%%%%%%%%%%%%%%%%%%%%%
% grafos: lito y charly, gps (regional para suecia)
% grafos: flujo oculto (angel & demons)
% tablero, grafo, greedy (problema ya escrito)
% eliminación gaussiana + probabilidades
% dijsktra con colita
% 
%
%
%
%%
%%
%%%%%%%%%%%%%%%%%%%%%%%

\begin{problema}
\begin{description}
 \item[Nombre] Deer-Proof Fence
 \item[Competencia] {\em ACM ICPC}. Final Mundial 2009. Estocolmo (Suecia)
 \item[Técnicas utilizadas] Cápsula convexa ({\em Convex Hull}), programación dinámica, máscaras de bits.
\end{description}
\end{problema}

\subsection*{Enunciado}
{\setlength{\parindent}{0in}

\begin{center}
{\huge Problem F}\\
\medskip
{\Large Deer-Proof Fence}\\
Input: fence.in 
\end{center}


Uncle Magnus has planted some young saplings on his farm as part of his reforestation project. Unfortunately,
deer like to eat tender sapling shoots and leaves, making it necessary to build protective fences around them.
Since deer and other sapling nibblers can reach partway over the fence, every fence must lie at least a minimum
distance (a margin) from each sapling.
Deer-proof fencing is quite expensive, so Uncle Magnus wants to minimize the total length of fencing used.
Your job is to write a program that computes the minimum length of fencing that is required to enclose and
protect the saplings. Fences may include both straight and curved segments. You may design a single fence that
encloses all saplings or multiple fences that enclose separate groups of saplings.
Figure 6 shows two example configurations, each consisting of three saplings with different margin
requirements. In the top configuration, which corresponds to the first sample input, the minimum-length solution
consists of two separate fences. In the bottom configuration, which corresponds to the second sample input, the
minimum-length solution consists of a single fence.

%imagen de enunciado
  \begin{center}
  \includegraphics[width=0.6\textwidth]{./img/fences.jpg} 
  \end{center}


\subsubsection*{Input}
The input consists of multiple test cases. The first line of each test case contains integers $N$ ($0 < N \le 9)$, which is
the number of saplings, and $M$ ($0 < M \le 200$), which is the margin required around each sapling. This line is
followed by $N$ additional lines. Each of these $N$ lines contains two integers $x$ and $y$ that describe the Cartesian
coordinates of a sapling ($|x| \le 100$ and $|y| \le 100$). No two saplings are in the same location. For simplicity the
saplings can all be considered as points and the thickness of deer-proof fences can be considered zero.
The last test case is followed by a line containing two zeros.

\subsubsection*{Output}
For each test case, print the case number (starting with $1$) followed by the minimum total length of fencing
required to protect the saplings with the given margin. Print the length with two digits to the right of the decimal
point. Follow the format of the sample output.

\inoutsamples
{3 2 \\
0 0 \\
2 0 \\
10 0 \\
3 4 \\
0 0 \\
2 0 \\
10 0 \\
0 0
}
{Case 1: length = 29.13 \\
Case 2: length = 45.13
}
}

\subsection*{Solución}

El primer detalle a tener en cuenta es que los puntos donde se encuentran los arbolitos ({\em saplings}) pueden modelarse como un círculo centrado
en ese punto de radio $M$ (el margen dado).

Supongamos ahora que disponemos de una sola cerca para cubrir la totalidad de estos arbolitos. 
Veamos qué forma toma la cerca más corta que los cubre.


% Insertar imagen y agregar colores a la explicación de abajo
\begin{center}
\includegraphics[width=0.7\textwidth]{./img/fence-explicacion2.jpg} 
\end{center}

Podemos ver que está compuesta de secciones rectas (tangentes a un par de círculos ``consecutivos") y por otras secciones que son arcos circulares.

Dado que la cerca da una vuelta completa alrededor de los círculos, los arcos circulares cubren en total una amplitud de $360^{\circ}$. Es decir que 
si pegáramos todos los arcos de la figura obtendríamos un círculo completo. La longitud de las secciones circulares será entonces la longitud de una 
circunferencia de radio $M$, o sea $2 \pi \cdot M$.

Para las secciones rectas, observamos que la longitud de la tangente a 2 circunferencias es igual a la del segmento que une sus centros. Por lo tanto
la longitud total de las líneas rectas de la cerca será igual al perímetro del polígono formado por los centros, es decir la posición de los arbolitos.
Debemos hallar entonces el polígono convexo más pequeño que encierra a todos los puntos considerados, este es un problema estándar de geometría computacional, 
recibe el nombre de {\em convex hull} (ver \cite{cormen} cáp. 33 sección 3). Puede utilizarse el {\em algoritmo de Graham} \cite{graham} que resuelve el problema en un tiempo 
de $O(n \log n)$ o la variante descubierta posteriormente por Andrew \cite{andrew} que resulta más simple de programar y tiene el mismo tiempo de ejecución.
siendo $n$ la cantidad de puntos considerados.
Nótese que no necesariamente todos los puntos a cubrir serán vértices de la {\em convex hull}.
\newline

Ya tenemos resuelto el caso de considerar una sola cerca. La longitud será: {\em perímetro de convex hull} $+$ {\em perímetro de circunferencia de radio $M$}.
Llamaremos a este subproblema soluciónSimple:

\begin{center}
soluciónSimple($C$) = ``mínima longitud necesaria para proteger los arbolitos del conjunto $C$ con una única cerca"
\end{center}

Para obtener la solución óptima solo nos resta considerar cuál es la mejor manera de {\em particionar} el conjunto de arbolitos de manera que cada 
parte sea cubierta por una sola cerca.

Dado el bajo número de arbolitos, una solución que pruebe todas las particiones posibles puede entrar en tiempo. Sin embargo, se puede realizar una
optimización sencilla que asegura un mejor tiempo de ejecución y permite considerar todas las particiones sin generarlas explícitamente.
Para esto, se plantea una solución con programación dinámica que resuelve el problema tomando como instancias todos los posibles conjuntos de arbolitos:

\begin{center}
solución($C$) = ``mínima longitud de cerca para proteger los arbolitos del conjunto $C$ (se permiten múltiples cercas)" 
\end{center}

El planteo recursivo tendrá la forma:
$$
\begin{array}{ l }
solucion(\emptyset) = 0 \\
solucion(C) = \min_{\emptyset \subset S \subseteq C} \left[solucionSimple(S) + solucion(C \setminus S)\right]
\end{array}
$$


El planteo de la solución dinámica es claro. Para cubrir todos los árboles del conjunto $C$ deberá suceder una de las siguientes situaciones:
\begin{itemize}
 \item El conjunto $C$ es vacío, en cuyo caso no habrá necesidad de usar cercas. La solución es $0$.
 \item El conjunto $C$ no es vacío y por lo tanto deberá ser cubierta por una o más cercas. Alguna de dichas cercas cubrirá un subconjunto $S \subseteq C$.
 Una solución óptima estará compuesta por una cerca que cubra a $S$ y una o más cercas que cubran a los arbolitos restantes del conjunto $C \setminus S$.
\end{itemize}
% \newline

La implementación de la solución requiere 2 partes.
En la primera, nos encargamos de precomputar {\em soluciónSimple} para todos los subconjuntos de los $n$ arbolitos dados. Luego usaremos estos 
valores para la etapa posterior de programación dinámica. Como dijimos antes, esto se limita a calcular la suma del perímetro de la {\em convex hull} 
y el de la circunferencia de radio $M$.
Dado que la cantidad de subconjuntos a considerar es $2^n$ y existen algoritmos que computan la {\em convex hull} en $O(n \log n)$, el tiempo
total empleado por esta primera fase estará en $O(2^n n \log n)$, lo cual es totalmente aceptable para los límites dados ($n \le 9$).

La segunda parte se encargará de computar {\em solución}, es decir la longitud de cerca utilizada en una partición optimal. El enfoque de programación 
dinámica que proponemos tendrá $2^n$ instancias (los subconjuntos posibles $C_i$ de árboles), a su vez en cada instancia se realiza un bucle que recorre
todos los subconjuntos $S_j \subseteq C_i$. Por lo tanto, el orden de tiempo de ejecución se calculará a partir de:

$$ 
\sum_{C_i \subseteq A} \sum_{S_j \subseteq C_i} 1 = \sum_{C_i \subseteq A} 2^{\left| C_i \right|} = 3^{\left| A \right|} \\
\text{siendo $A$ el conjunto de arbolitos.} 
$$

El cálculo de esta sumatoria no es trivial. Una manera bastante intuitiva de pensarlo es como la cantidad de pares de conjuntos $(S,C)$ tal que
$S \subseteq C \subseteq A$. Luego, cada elemento de $A$ cumple exactamente una de las siguientes condiciones:
\begin{itemize}
\item solo pertenece al conjunto $S$
\item pertenece al conjunto $C$ pero NO a $S$
\item no pertenece ni a $S$ ni a $C$
\end{itemize}

A partir de la condición que cumple cada elemento quedan unívocamente determinados $S$ y $C$, por lo tanto la cantidad de elecciones posibles será
$3^{\left| A \right|}$.
El cómputo de la parte de programación dinámica se realizará en un tiempo de $O(3^n)$ lo cual también es aceptable para $n \le 9$.
\newline

La representación ideal para las instancias de la dinámica serán las máscaras de bits, dado que trabajamos con subconjuntos de un
conjunto fijo de a lo sumo 9 elementos. La utilización de bitmask facilita tareas como iterar sobre todos los subconjuntos de un cierto conjunto
y lograr acceso indexado a una tabla con los valores de solución para cada instancia. Para más detalles, consultar la sección de {\em Máscaras de bits}
del próximo capítulo.

El valor de la solución queda determinado por el valor de la dinámica en la instancia que abarca a todos los arbolitos: {\em solución}$(A)$.
El tiempo tomado por el programa será de $O(2^n \log n + 3^n) = O(3^n)$.

%%%%%%%%%%%%%%%%%%%
% EMOTICONS
 
\begin{problema}
\begin{description}
 \item[Nombre] Emoticons :-)
 \item[Competencia] {\em ACM ICPC}. Regional Sudaméricana 2007.
 \item[Técnicas utilizadas] String matching, algoritmos greedy.
\end{description}
\end{problema}



\begin{center}
{\huge Problem E}\\
\medskip
{\Large Emoticons :-)}\\
{\em Source file name:} emoticons.c, emoticons.cpp or emoticons.java
\end{center}

\subsection*{Enunciado}

{\setlength{\parindent}{0in}
Emoticons are used in chat and e-mail conversations to try to express the emotions that printed
words cannot. This may seem like a nice feature for many, but a lot of people find it really
annoying and wants to get rid of emoticons.
George is one of those people. He hates emoticons so bad, that he is preparing a plan to
remove all emoticons from all e-mails in the world. Since you share his visionary plans, you are
preparing a special program to help him.
Your program will receive the list of emoticons to proscribe. Each emoticon will be a string of
characters not including any whitespace. You will also receive several lines of text. What you
need to do is change some characters of the text into spaces to ensure no emoticon is left on
the text. For an emoticon to be considered to appear in the text it has to appear in a single
line and be made of consecutive characters.
To help George’s plan remain secret as long as possible, you need to do your job with the
minimum possible amount of character changes.

\subsubsection*{Input}
The input file contains several test cases. Each test case consists of several lines. The first
line of each test case will contain two integers separated by a single space: N, the number of
emoticons to proscribe, and M, the number of lines the text has. The next N lines contain one
emoticon each, a non-empty string of at most 15 characters. Each of the last M lines of the
test case contains a line of text of at most 80 characters. You can assume 1  N,M  100.
Valid input characters for emoticons are uppercase and lowercase letters, digits and the symbols
``\verb|!?.,:;-_’#$%&/=*+(){}[]|" (quotes for clarity). Each line of the text may contain the same
characters with the addition of the space character.

The input is terminated by N = M = 0.

{\em The input must be read from standard input.}


\subsubsection*{Output}
For each test case, output exactly one line containing a single integer that indicates the minimum
number of changes you need to make to the entire text to ensure no emoticon on the list appears
in it.

{\em The output must be written to standard output.}

\subsubsection*{Sample Input}
{\small
\begin{verbatim}
4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0
\end{verbatim}
}

\subsubsection*{Output for the sample Input}
{\small
\begin{verbatim}
11
8 
\end{verbatim}
}
}



\subsection*{Solución}

Como primera observación notamos que el problema involucra encontrar las ocurrencias de una cadena de texto (emoticones) dentro de una cadena mayor 
(líneas de texto). Este subproblema es conocido como {\em string matching} o {\em pattern matching} y puede consultarse en la bibliografía 
\cite{cormen} (cap. 32).
Existen numerosos algoritmos destinados a la resolución de este problema. El más simple de ellos es un algoritmo de fuerza bruta que corre en $O(mn)$, 
siendo $m$ la longitud de la cadena buscada ({\em patrón}) y $n$ el tamaño de la cadena escaneada ({\em texto}).
Existen algoritmos más sofisticados como Boyer-Moore \cite{boyer}, Knuth-Morris-Pratt \cite{kmp} y Aho-Corasick \cite{aho} que resultan muy eficientes 
en ciertos contextos.
\newline

Dados los límites impuestos en este problema, la opción de aplicar el algoritmo de fuerza bruta resulta viable. Podemos calcular que, en el peor caso, se 
ejecutarán un total de $15 \times 80 \times 100 \times 100 = 12.000.000$ de operaciones, lo cual suele resultar aceptable en este tipo de competencias.
Otra opción que resulta muy cómoda de implementar, es utilizar la operación {\tt find} que se encuentra implementada en la clase {\tt string} de 
{\em STL}.
\newline

El enunciado explicita que un emoticón debe encontrarse en una única línea, por lo tanto podemos trabajar sobre cada línea de texto independientemente.
Luego de computar todas las apariciones de emoticones en la línea el problema puede ser modelado como un conjunto de intervalos $[a_i,b_i]$, donde cada 
intervalo representa un emoticón que se extiende desde la posición $a_i$ a la $b_i$. Nuestro objetivo será hallar la mínima cantidad de posiciones 
${x_1, x_2, \ldots x_k}$ (donde ubicaremos los espacios en blanco) tal que para todo intervalo $[a_i,b_i]$ exista un $x_j$ tal que $x_j \in [a_i,b_i]$, 
de manera de asegurar que no existan emoticones en el texto resultante.

Podemos encarar la resolución de este problema con una estrategia {\em greedy}. 
Consideremos el intervalo $[a_i,b_i]$ que finaliza primero (i.e. cuyo valor $b_i$ sea el más pequeño). Es claro que debe existir un espacio en blanco
en alguna posición del intervalo $[a_i,b_i]$. Dado que el resto de los intervalos finalizan después, una elección óptima es colocar el espacio en la
posición $b_i$, elegir una posición menor no nos implicaría ventaja alguna. Luego podemos descartar todos los intervalos que fueron cubiertos por el 
espacio colocado y continuar considerando los restantes. Siguiendo esta estrategia hasta que no queden intervalos por cubrir hallaremos una solución
óptima.

La implementación de este algoritmo resulta bastante simple. 
Primero debemos ordenar los intervalos según el valor de su extremo derecho en forma creciente. 
Luego recorremos la lista deteniéndonos en cada intervalo que aún no fue cubierto por un espacio, incrementamos el contador de espacios usados y 
actualizamos el valor de la última posición cubierta.
La ordenación de $n$ intervalos toma un tiempo de $O(n \log n)$ y el recorrido se realiza en un tiempo de orden lineal. 
Por lo tanto, el tiempo de ejecución total estará en $O(n \log n)$.
Considerando que cada línea tiene a lo sumo 80 caracteres, la cantidad total de intervalos estará acotada por $80^2 / 2 = 3200$.
Concluyendo, en el peor caso se ejecutarán 100 veces (máximo número de líneas) un algoritmo $O(n \log n)$ con $n \le 3200$ lo cual resulta suficiente.
\newline

Una opción conveniente para almacenar y ordenar los intervalos es utilizando un {\tt vector} de \verb|pair<int,int>|.
De esta manera no necesitamos implementar nuestra propia clase o registro y sacamos provecho de la comparación por defecto de la clase {\tt pair}.
Para lograr el ordenamiento propuesto, debemos guardar como primer elemento el extremo derecho. El intervalo $[a_i,b_i]$ será representado como
{\tt make\_pair(bi,ai) }.


\chapter{Detalles de implementación}

En este capítulo revisaremos algunas técnicas y consejos útiles a la hora de programar en competencias.
Para ilustrar estas técnicas hemos elegido el lenguaje C++ porque sigue siendo el más popular entre los participantes de estas competencias, 
porque provee herramientas que permiten programar de una manera muy compacta y eficiente, y sobre todo porque es el que elegimos a la 
hora de competir.

Debemos tener en cuenta que el objetivo es generar un código de manera veloz y que sea simple de leer, entender y depurar.
El código en estas pruebas se utiliza una única vez, no es parte de un proyecto en el que intervienen muchas personas; el jurado no evalúa 
la calidad del código y la prioridad está puesta en la velocidad para programar. Por lo tanto, no es necesario apelar a un diseño modular, 
modificable o reutilizable.

También haremos un breve repaso de las estructuras de datos que nos proveen las librerías estándar de C++ (\emph{STL}) y cuyo manejo nos 
permitirá ahorrar tiempo y código.

Al final del capítulo veremos ejemplos de implementaciones de algoritmos y estructuras de datos que se simplifican 
enormemente al utilizar estas técnicas.

\section{Utilización de macros y definiciones de tipo}

C++ provee una funcionalidad que resulta de extrema utilidad para simplificar el código: la \emph{macro}.
Las \emph{macros} permiten abreviar sentencias de código frecuentemente utilizadas, esto nos permite ahorrar tiempo de codificación.
Una construcción similar a las macros que sirve a este mismo objetivo son las definiciones de tipo por el usuario: \emph{typedef}.

La utilización de estos ``trucos'' para ahorrar código puede resultar un poco confusa para el programador que no esté familiarizado.
Sin embargo, una vez que uno se acostumbra a programar de esta manera, los códigos resultan mucho más claros, concisos e incluso declarativos.

Existe un conjunto de macros y typedef que es utilizado por la mayoría de los programadores de la comunidad algorítmica, pueden existir algunas
diferencias en cuanto a los nombres usados pero en esencia son iguales. Por lo tanto, esta práctica no resulta un obstáculo para leer código ajeno.

\subsection*{Definiciones de tipos: typedef}

\noindent Algunas de los \emph{typedef} que nos resultan convenientes son:

{\small
\begin{verbatim}
typedef long long int tint; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<tint> vt; 
typedef vector<vt> vvt; 
typedef vector<double> vd; 
typedef vector<vd> vvd; 
typedef vector<bool> vb; 
typedef vector<vb> vvb; 
typedef vector<string> vs; 
typedef pair<int,int> pii; 
\end{verbatim}
}

En algunos problemas es necesario trabajar con enteros de 64 bits para lograr una solución correcta, \texttt{tint} resulta muy útil en estos casos
porque nos ahorra de escribir \texttt{long long int} en varios lugares del código.

\texttt{vector} es la implementación de \emph{STL} de las tablas dinámicas. Este tipo es muy utilizado y hallamos conveniente tener definiciones de
tipo para los \emph{vector} y \emph{vector de vector} de cada tipo básico.

Por último, el par de enteros es una estructura práctica para manipular datos en diversas situaciones.

\subsection*{Macros: \#define}

\subsubsection*{Bucle \emph{for}: \texttt{ forn, forsn, dforsn}}
% \subsubsection*{Macros for}

{\small
\begin{verbatim}
#define forn(i,n) for(int i=0;i<(int)(n);i++) 
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++) 
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--) 
\end{verbatim}
}


El bucle \texttt{for} es probablemente la construcción que se utiliza con más frecuencia en programas de naturaleza algorítmica.
Si bien el \texttt{for} de C++ es muy flexible para realizar diferentes tipos de iteraciones, la mayoría de las veces se utiliza 
para recorrer los enteros de un intervalo del tipo $[0,n)$. Otros casos muy frecuentes son el recorrido del intervalo $[s,n)$ tanto 
en sentido creciente como decreciente. 
\\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
//Imprime todos los primos menores a 100
forn(x,100)
  if (es_primo(x))
    cout << x << endl;


// Recorrido de una tabla en Programación Dinámica
// en dirección creciente de filas y decreciente columnas
forsn(i,1,n) dforsn(j,1,n)
   T[i][j] = calcular(T[i-1][j], T[i][j+1]);
\end{verbatim}
}


\subsubsection*{Tamaño: \texttt{si}}

{\small
\begin{verbatim}
#define si(c) ((int)(c).size())
\end{verbatim}
}

En C++, el método \emph{size()} devuelve el tamaño de \emph{string}, \emph{vector}, \emph{map} y casi cualquier otra colección ofrecida en STL.
Suele utilizarse combinada con un \texttt{forn} para iterar sobre los elementos de una colección o los caracteres de un \emph{string}.
El problema que presenta, es que el tipo devuelto por \emph{size()} es un entero no signado. Por lo tanto puede traer complicaciones en caso de que 
se compare con un índice signado que tome un valor negativo.
\\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
typedef vector<int> vi;
vi a;
...
// Imprime todos los elementos de un vector
forn(i,si(a)) cout << a[i] << endl;
\end{verbatim}
}

\subsubsection*{Declaración de variables: \texttt{decl}}
{\small
\begin{verbatim}
#define decl(v, c) typeof(c) v = c 
\end{verbatim}
}

En ocasiones, especialmente cuando se trabaja con \emph{iteradores} de las colecciones provistas por la \emph{STL}, los nombres de los 
tipos a utilizar son demasiado largos y oscurecen el código. La macro \texttt{decl} hace uso del operador \texttt{typeof} brindado por
algunas versiones del compilador \emph{GCC} y constituye una herramienta adecuada para simplificar el programa.
\\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
map<pair<int,int>, double> a;
...
// Declara e inicializa el iterador it apuntando al inicio del map a
map<pair<int,int>, double>::iterator it = a.begin()

// Código equivalente utilizando la macro decl
decl(it,a.begin())
\end{verbatim}
}

\subsubsection*{Recorrido genérico de estructuras de STL: \texttt{forall} y \texttt{dforall}} 


{\small
\begin{verbatim}
#define forall(i, c) for(decl(i, c.begin()); i!=c.end(); ++i) 
#define dforall(i, c) for(decl(i, c.rbegin()); i!=c.rend(); ++i) 
\end{verbatim}
}

Los iteradores de STL proveen un mecanismo genérico para acceder a los elementos de sus colecciones.
Como mencionamos anteriormente, los nombres de los tipos de estos iteradores son muy largos y pueden perjudicar la claridad del código.
Haciendo uso de \texttt{decl} podemos definir las macros \texttt{forall} y \texttt{dforall} que permitirán recorrer una colección de manera 
creciente y decreciente respectivamente.
\\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
set<int> M;
...
// Imprime los elementos de M de manera creciente
forall(it,M) cout << *it << endl;

// Imprime los elementos de M de manera decreciente
dforall(it,M) cout << *it << endl;
\end{verbatim}
}


\subsection*{Pares de iteradores: \texttt{all} y \texttt{rall}}

{\small
\begin{verbatim}
#define all(c) (c).begin(), (c).end() 
#define rall(c) (c).rbegin(), (c).rend() 
\end{verbatim}
}

STL ofrece algoritmos estándar implementados genéricamente como el ordenamiento y la búsqueda binaria.
Para lograr este tratamiento genérico de colecciones estas funciones requieren que se les pase un par de iteradores: de comienzo y de final.
\\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
typedef vector<int> vi;
vi x;

// Ordena de forma creciente los elementos de x
sort(all(x));

// Ordena de forma decreciente los elementos de x
sort(rall(x));

// Búsqueda binaria de un valor en x
if (binary_search(all(x),10))
  cout << "Encontramos el 10" << endl;
\end{verbatim}
}

\subsubsection*{Otras: \texttt{pb} y \texttt{mp}}

{\small
\begin{verbatim}
#define pb push_back 
#define mp make_pair 
\end{verbatim}
}

Métodos como \texttt{push\_back} y \texttt{make\_pair} son frecuentemente utilizados pero su nombre resulta algo incómodo, es por esto
que se justifica la utilización de una macro para invocarlos.
\\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
typedef pair<int,int> pii;
typedef vector<pii> vpii;

// Genera una lista de pares de elementos (x,x^2)
vpii pares;
forn(x,100) pares.pb(mp(x,x*x));
\end{verbatim}
}

% - construcciones casi matem abstractas: como forn(i,n) forn(j,n) if (f(i,j) = true)
% 
% >? max a = max(a,b) a >?= b
% <? = min

\section{Máscaras de bits}

Como mencionamos anteriormente, las competencias de programación apuntan al diseño de algoritmos eficientes en cuanto a su orden asintótico pero
no suelen requerir optimizaciones de bajo nivel. Sin embargo, existen ciertas excepciones en las que la utilización de técnicas de bajo nivel dan 
como resultado un significativo aumento de la eficiencia y claridad del código además de facilitar la tarea de implementación.

Este es el caso de las \emph{máscaras de bits} o \emph{bitmasks}. Éstas constituyen una práctica herramienta para representar y operar sobre 
el tipo de datos \emph{conjunto}. En particular, son frecuentemente usadas para implementar técnicas de programación dinámica sobre subconjuntos.


\subsubsection*{Fundamentos}

En general las máscaras de bits se utilizan para representar subconjuntos de un conjunto fijo. Si el conjunto tiene $n$ elementos será necesaria
una máscara de $n$ bits.
Cada bit de la variable utilizada está asociado a un elemento del conjunto y tendrá el valor $0$ para indicar que el elemento está ausente 
o $1$ en caso contrario.

Si tenemos el conjunto $C = {c_1,c_2, \ldots, c_n}$, el subconjunto $S \subseteq C$ será representado por la máscara $M$ que se define como: \\

$$ M = \sum_{i=0}^{n-1} x_i \cdot 2^i \text{ con } 0 \le x_i \le 1 $$

siendo


\begin{displaymath}
   x_i = \left\{
     \begin{array}{lr}
       1 & : c_i \in S \\
       0 & : c_i \notin S
     \end{array}
   \right.
\end{displaymath} 

El manejo de máscaras de bits se efectúa a través de tipos de datos enteros (\texttt{int} o \texttt{tint}) y los operadores a nivel de bits 
(\emph{bitwsise operators}):
\begin{itemize}
 \item and: \verb|&|
 \item or: \texttt{|}
 \item xor: \verb|^|
 \item not: \verb|~|
 \item shift left: \verb|<<|
 \item shift right: \verb|>>|
\end{itemize}
% \marginpar{agregar operadores}

Las operaciones sobre conjuntos se pueden implementar del siguiente modo utilizando \emph{bitmasks} y \emph{bitwise operators}:

\begin{itemize}
\item Unión de conjuntos: $A \cup B$ = \texttt{A | B}%A \mid B$
\item Intersección de conjuntos: $A \cap B$ = \texttt{A \& B} % A \And B$
\item Diferencia de conjuntos: $A \setminus B$ = \texttt{A \& \~{}B}
\item Diferencia simétrica: $A \Delta B$ = \verb|A ^ B|
\item Conjunto universal: \verb|ALL_BITS = (1<<n) - 1|
\item Complemento: $\bar{A}$ = \verb|ALL_BITS ^ A|
\item Agregar elemento: $A \cup \{ a_i\}$ = \texttt{A |} \verb|(1 << i)|
\item Quitar elemento: $A \setminus \{ a_i\}$ = \verb|A & ~(1<<i)| %|A hatcito 1 shiftleft (i)$
\item Chequear inclusión $A \subseteq B \iff$ \verb|(A & B) == A| %(A \And B) = A$
\item Chequear pertenencia $ a_i \in A \iff$ \verb|(A & (1 << i)) != 0|
\end{itemize}


Vale aclarar que es necesario ser cuidadoso en la parentización de las expresiones que operan a nivel de bits.
Esto se debe a que en el standard de {\em C/C++} las comparaciones y los corrimientos ({\em shifts}) tienen precedencia sobre los 
operadores {\em and, or} y {\em xor}. 
Por lo tanto, \verb|A & 1 << i| será interpretado como \verb|(A & 1) << i| y \verb|A & B == 0| como \verb|A & (B == 0)| lo cuál será probablemente
incorrecto. La falta de paréntesis en una expresión de este tipo es uno de los errores más comunes cuando se trabaja con {\em bitmasks}.

\subsubsection*{Otras operaciones}

El compilador \emph{GCC} ofrece algunas funciones menos conocidas que resultan útiles para trabajar sobre máscaras de bits. Estas son:
\begin{itemize}
 \item \verb|int __builtin_clz (unsigned int x)|: La regla mnemónica es {\em clz} = ``count leading zeros".
Como su nombre lo indica, esta función retorna la cantidad de {\em bits} con valor $0$ al inicio de la representación binaria de su argumento.

Esto resulta particularmente útil para realizar cálculos del estilo $\lfloor \log_2 n\rfloor$. 
El valor será \verb|31 - __builtin_clz(n)| si $n$ es un entero de $32$ {\em bits} \\
o \verb|63 - __builtin_clz(n)| para el caso de $64$ {\em bits}.

\item \verb|int __builtin_ctz (unsigned int x)|: En este caso, {\em ctz} = ``count trailing zeros".
Resulta conveniente para averiguar cuál es la mayor potencia de 2 que divide a un cierto entero.

Existen algunos algoritmos específicos, como las operaciones de inserción y eliminación en un \emph{Binary Indexed Tree}, que requieren computar
la {\em bitmask} con la posición menos significativa donde haya un $1$. Por ejemplo, para $232 = (11101000)_2$ queremos obtener $8 = (00001000)_2$.
La función \verb|__builtin_ctz| podría utilizarse en este caso. Sin embargo, podemos usar una técnica más conveniente que se basa en la representación en 
{\em 2-complemento}.
Si realizamos el calculo \verb|x & (-x)|, dadas las propiedades del {\em 2-complemento}, obtendremos precisamente la máscara de bits buscada.

\item \verb|int __builtin_popcount (unsigned int x)|: {\em popcount} se encarga de contar la cantidad de bits seteados en $1$
que tiene un entero. Claramente, se puede utilizar para calcular de manera rápida la cardinalidad de un conjunto representado por 
una {\em máscara de bits}.

\end{itemize}

Estas operaciones, podrían ser implementadas fácilmente a partir de los {\em bitwise operator} estándar que vimos en la sección anterior. 
El valor de estas funciones -- tan poco conocidas -- reside en su eficiencia. Las operaciones de {\em scanning de bits} (clz y ctz) son implementadas 
directamente a nivel hardware y la función de {\em conteo de bits} (popcount) se basa en una búsqueda en una tabla precomputada por lo cual resultan 
en extremo eficientes.

\subsubsection*{Recorriendo todos los subconjuntos}

Muchas veces resulta necesario iterar sobre todos los subconjuntos de un conjunto.
Aquí, la representación de {\em bitmask} resulta muy ventajosa ya que la iteración sobre subconjuntos puede implementarse fácilmente
y de manera eficiente.

Si queremos iterar con una variable \verb|S| sobre todos los subconjuntos del conjunto representado por la variable \verb|C|, solo hace falta
el siguiente bucle:

{\small
\begin{verbatim}
for (int S = C; S > 0; S = (S-1) & C}
  .....
\end{verbatim}
}

La clave está en la actualización de la variable: \verb|S = (S-1) & C|.
Al restarle $1$ a \verb|S| el bit menos significativo que estaba en $1$ toma el valor $0$ y todos los
bits posteriores toman el valor $1$. Luego realizar el {\em bitwise and} con \verb|C| asegura que la máscara 
obtenida siga siendo subconjunto de \verb|C|. De esta manera, \verb|S| recorrerá todos los subconjuntos de \verb|C| en 
orden decreciente.

\subsubsection*{Máscaras de bits más grandes: \texttt{bitset}}

La librería estándar de C++, la {\em STL}, brinda un tipo de datos que resulta una extensión de las {\em bitmasks} en cuanto a su longitud.
Con los tipos de datos enteros más las operaciones a nivel de bits teníamos un límite de 32 o 64 bits.
El {\tt bitset} implementa máscaras de bits de longitud arbitraria.
Provee implementaciones para todas las operaciones básicas a nivel bit ({\em and, or, xor, not, \ldots}). Adicionalmente, provee algunas
funcionalidades extra como acceso indexado a bits. 
Internamente, la representación de \verb|bitset| es una lista o tabla de enteros. Las operaciones se implementan a partir de las operaciones de 
manipulación de bits básicas (que están implementadas en el {\em hardware}), repitiendo la operación básica para toda la lista.
Por este motivo, operar con {\tt bitset} resulta en un incremento de performance si lo comparamos con una implementación basada en un arreglo de 
variables booleanas.
\newline 

Generalmente, las soluciones que utilizan máscaras de bits tienen un orden en tiempo de ejecución exponencial y solo son aplicables a
conjuntos de no más de 20-25 elementos. Por este motivo, la cantidad de bits necesaria no suele ser una limitación real como para usar \verb|bitset| 
en lugar de enteros.

Podemos identificar 2 razones para utilizar {\tt bitset}. Por un lado, algunos problemas requieren la manipulación de conjuntos grandes sin implicar
una solución de tiempo exponencial. Por otra parte, algunos participantes encuentran este tipo de datos más fácil y cómodo de usar debido a su capacidad 
de acceder a cada bit mediante un índice.

%Ejemplos de problemas con bitmask

\section{Librería estándar (STL)}

La Standard Template Library ({\em STL}) de C/C++ es una de las herramientas más potentes que ofrece este lenguaje para programar en el contexto de una
competencia de algoritmos. Se trata de una extensa librería que brinda múltiples opciones en cuanto a estructuras de datos implementadas y que 
también posee funciones para una variedad de algoritmos útiles.

Su utilización nos facilitará la tarea de implementación, logrando códigos más simples y compactos que toman menos tiempo de programación y depuración.
Creemos fundamental lograr un manejo básico de los contenidos de la {\em STL} para lograr un nivel de competitivad aceptable.

\subsection*{Estructuras de datos}

Para la implementación de numerosos algoritmos es necesario utilizar ciertas estructuras de datos que hacen posible nuestra tarea. La {\em STL}
nos provee de poderosas estructuras de datos ya implementadas que serán de gran utilidad a la hora de programar.


\subsubsection*{vector}

El {\tt vector} es la implementación de tablas dinámicas ofrecida por la {\em STL}.
Es similar al arreglo pero presenta algunas ventajas: permite modificar su tamaño en tiempo de ejecución, se puede consultar su tamaño, 
soporta inserciones en cualquier lugar de la secuencia (en orden lineal en la cantidad de elementos), entre otros.

Posee operaciones especiales para insertar y eliminar elementos al final de la secuencia. Estas tienen un tiempo
de ejecución amortizado constante. Cabe destacar que este \emph{container} requiere más memoria que un arreglo,
 pudiendo ocupar hasta el doble de espacio.  

Esta estructura es una de las más usadas en competencias de programación, e incluso nos vemos forzados a utilizarla en los certámenes
organizados por Topcoder, ya que los datos de entrada y salida suelen estar contenidos en \texttt{vectors}.
\\ \\
\subtitulo{Operaciones:} 
\\ \\
size(): Retorna la cantidad de elementos en el vector. \\ \\
push\_back(x): Agrega el elemento x al final del vector. \\ \\ 
pop\_back(); Elimina el último elemento del vector. \\ \\
insert(position,x): Inserta el elemento x en la posición dada. \\ \\
erase(position): Elimina el elemento que se encuentra en la posición dada. \\ \\
erase(first,last): Elimina los elementos en un dado rango.  \\ \\
operator[] (vect[i]): Retorna una referencia al i-ésimo elemento del vector.\\ \\
clear(); Vacía el vector. \\ \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}

typedef vector<int> vi;

vi v (17,100); //Crea un vector con 17 elementos 100
v.clear(); //Vacía el vector

forn(i,5) v.push_back(i);
//v = [0,1,2,3,4]

v.insert(v.begin()+2,45);
//v = [0,1,45,2,3,4]

v.erase(v.begin()+1);
//v = [0,45,2,3,4]

v.pop_back();
//v = [0,45,2,3]

//Imprime los elementos del vector
forn(i,v.size()) cout<<v[i]<<"";

\end{verbatim}
}


\subsubsection*{string}

Un {\tt string} es un \emph{container} diseñado específicamente para trabajar con secuencias de caracteres. 
A diferencia de los strings en C, que son simplemente arreglos de caracteres, los strings provistos
por la STL poseen varias funciones adicionales que permiten operar de una forma más cómoda e intuitiva.
\\ \\
\subtitulo{Operaciones:} 
\\ \\
size(): Retorna la cantidad de caracteres en el string. \\ \\
operator[] (cadena[position]): Retorna el caracter que se encuentra en la posición dada.\\ \\
operator+: Es el operador de concatenación. \\ \\
replace(pos,n,str): Reemplaza una sección de la cadena actual por otra cadena. Serán reemplazados
los caracteres en el rango [pos,pos+n-1] por la cadena str. \\ \\
find(str): Busca en la cadena actual por el contenido especificado en str y retorna la posición de la 
primera aparición dentro de la cadena. \\ \\
substr(pos,n): Retorna la subcadena que comienza en pos y posee un tamaño n.\\ \\
compare(str): Compara alfabéticamente el string actual con str. Retorna 0 si las cadenas son iguales, 
un valor negativo si la cadena actual es menor que la recibida y un valor positivo en caso contrario.\\ \\
c\_str(): Retorna el string correspondiente en formato C, es decir, un  arreglo de caracteres. \\ \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
  string s = "hola ";
  //s = "hola "

  s+= "mundo";
  //s = "hola mundo"
  
  s.replace(5,5,"MUNDO");
  //s = "hola MUNDO"
  
  string t = s.substr(3,5);
  //t = "a MUN"

  inf found = s.find("la");
  if (found!=string::npos) 
    cout<<"Se encontró la subcadena buscada"<<endl;
  
  //Cuenta la cantidad de letras 'a' en el string
  int cantidad = 0;
  forn(i,si(s)) if (s[i]=='a') cantidad++;
  
  if (s.compare("Algoritmos")<0) 
    cout<<s<<" es menor que /"Algoritmos/""<<endl;
  

\end{verbatim}
}


\subsubsection*{set}

La {\em STL} implementa conjuntos mediante el \emph{container} \texttt{set}. Esta estructura nos permite
agregar, remover y consultar por la presencia de un determinado elemento en $O(\log n)$, donde $n$ es
la cantidad de elementos en el \texttt{set}. El \texttt{set} está implementado internamente con un
 \emph{Red-Black Tree} \cite{cormen}(cap. 14), lo cual lo hace altamente eficiente.
Otro detalle a destacar es que los iteradores de \texttt{set} recorren la estructura en forma
ordenada, característica que resulta de gran utilidad en varias situaciones, como veremos
más adelante. 
\\ \\
\subtitulo{Operaciones:} 
\\ \\
size(): Retorna la cantidad de elementos en el set.\\ \\
insert(x): Inserta el elemento x en el set. Si x ya pertenece al set, esta operación no tiene 
efecto alguno. \\ \\
erase(position): Elimina el elemento que se encuentra en la posición dada. \\ \\
erase(first,last): Elimina los elementos en un dado rango. \\ \\
erase(element): Elimina un elemento dado. \\ \\
clear(): Vacía el set. \\ \\
find(x): Busca el elemento x en el set. \\ \\  
count(x): Cuenta la cantidad de apariciones de x en el set. Dado que el set no permite elementos
repetidos, la utilización de esta operación no tendría sentido, ya que siempre retornará 1 o 0. Sin 
embargo, se suele utilizar en competencias de programación debido a que es más sencilla de escribir.\\ \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}

set<int> s;

//Inserta los números 0...999 en el set
forn(i,1000) s.insert(i); 

s.insert(10); //no hace nada, ya que 10 pertenece al set

//Elimina los números pares
forn(i,500) s.erase(i*2);

//Elimina el número 37
s.erase(37);

//Elimina los números en el intervalo [11,25)
#define decl(v, c) typeof(c) v = c 
decl(it1,s.begin());
decl(it2,s.begin());
it1 = s.find(11);
it2 = s.find(25); 
s.erase(it1, it2);


//Calcula la suma de los elementos en el set
int suma = 0;
for(set<int>::const_iterator it = s.begin(); it != s.end(); it++)
  suma += *it; 

//Forma equivalente utilizando macros 
forall(it,s) suma += *it;

//Consulta si 77 está en el set
if (s.find(77) != s.end()) ...

//Forma equivalente utilizando count
if (s.count(77)) ... // Más fácil de escribir!

//Imprime los elementos de un vector en forma ordenada
//y sin contar repetidos
vi v;
...
//Inicializa el set con los elementos de v
set<int> s(all(v)); 
forall(it,s) cout<<*it<<" ";

\end{verbatim}
}


\subsubsection*{map}

El \texttt{map} es un \emph{container}  similar al \texttt{set} pero difiere de este último
en que, en vez de contener solo valores, contiene pares (clave,valor). Cada par contenido en
un \texttt{map} tendrá una clave distinta.
Al igual que el \texttt{set}, el \texttt{map} está implementado con un \emph{Red-Black Tree}, 
soportando las operaciones de inserción, eliminación y consulta en $O(\log n)$, siendo $n$
la cantidad de elementos en el \texttt{map}.
De la misma forma que los iteradores del \texttt{set} recorren la estructura en forma ordenada, 
el \texttt{map} se recorrerá en orden ascendente de las claves de los elementos.

La utilización del operador [] nos permite trabajar de una manera similar a la que estamos
acostumbrados cuando usamos arreglos o vectores solo que, en lugar de mapear enteros en cualquier tipo, 
estaremos mapeando cualquier tipo en cualquier otro tipo.
\\ \\
\subtitulo{Operaciones:} 
\\ \\
size(): Retorna la cantidad de elementos en el map.\\ \\
erase(position): Elimina el elemento que se encuentra en la posición dada. \\ \\
erase(first,last): Elimina los elementos en un dado rango. \\ \\
erase(clave): Elimina el elemento que posee la clave dada. \\ \\
clear(): Vacía el map. \\ \\
operator[] (mapeo[x]): Si x es la clave de un elemento del map, retorna una referencia al valor mapeado a x.
Caso contrario, inserta un nuevo elemento en el map con clave x y el valor por defecto. Este operador
es de vital importancia, ya que nos permite trabajar muy cómodamente con un map, a diferencia de otros
lenguajes sin sobrecarga de operadores, como Java.\\ \\
find(x): Busca el elemento con clave x en el map. \\  \\
count(x): Cuenta la cantidad de apariciones de elementos con clave x en el map. 
Acá sucede lo mismo que con el count de set, aunque no tiene sentido utilizar esta operación, 
se la usa debido a que es más fácil de codificar. \\ \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
map<string,int> edad;

//Inserta un nuevo elemento al map
edad["Nicolás A."] = 27;

//Idem utilizando insert
edad.insert ( pair<string,int>("Nicolás K.",22) ); 

edad["Thomas Cormen"] = edad["Nicolás A."] + edad["Nicolás K."];

//Nicolás K. cumple años
edad["Nicolás K."]++;

//Pasó un año, la edad de todos aumentó en 1
forall(it,edad) it->second++;

//Elimino un elemento del map
edad.erase("Nicolás A.");

//Consulta por la presencia de un elemento con una clave dada
if (count("Nicolás A.")) ... 

Observación: 
edad["juan"] = edad["pedro"] + edad["ernesto"]; //C++
edad.put("juan",edad.get("pedro")+edad.get("ernesto")); //Java

\end{verbatim}
}


\subsubsection*{queue}

El \emph{container}  \texttt{queue} es la implementación de la Cola, una estructura secuencial que soporta inserciones
y extracciones y opera en modo FIFO (first-in first-out). Todas las operaciones tienen un tiempo de ejecución constante.
Este tipo de estructura se utiliza con frecuencia en competencias de programación, por lo cual es importante tener un cierto 
manejo de este \emph{container}. 
\\ \\
\subtitulo{Operaciones:} 
\\ \\
size(): Retorna la cantidad de elementos en el queue.\\ \\ 
front(): Retorna el primer elemento del queue.\\ \\
back(): Retorna el último elemento del queue.\\ \\
push(x): Agrega el elemento x al final del queue.\\ \\
pop(): Elimina el primer elemento del queue.\\ \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}

//Implementación de un BFS utilizando la estructura queue
int CANT_NODOS;
int color[CANT_NODOS];
forn(i,CANT_NODOS) color[i]= 0;
//0 = blanco, 1 = gris, 2 = negro

vvi adj; 
//matriz de adyacencia: adj[i][j] = j-ésimo vecino del nodo i

int ini = 0; //nodo inicial para el recorrido BFS
color[ini] = 1;

queue<int> Q;
Q.push(ini);

while(Q.size()>0) {
  int actual = Q.front();
  Q.pop();
    
  if (color[actual]==2) continue; //si es negro lo ignoro
  color[actual] = 2; //visita el nodo y lo pinta de negro	
  cout<<"visitando "<<actual<<endl;

  //Agrega a los vecinos blancos y los pinta de gris
  forn(i,adj[actual].size()) {
    int vecino = adj[actual][i];
    if (color[vecino] == 0) {
      color[vecino ] = 1; 
      Q.push(vecino);
    }
  }
}
\end{verbatim}
}


\subsubsection*{stack}

El \texttt{stack} es similar al \texttt{queue}, pero en lugar de tener un criterio de inserciones y extracciones FIFO, opera
en un contexto LIFO (last-in first-out). Al igual que en el \texttt{queue}, todas las operaciones tienen tiempo de ejecución constante.
\\ \\
\subtitulo{Operaciones:} 
\\ \\
size(): Retorna la cantidad de elementos en el stack. \\ \\
top(): Retorna el elemento que se encuentra en el tope del stack.\\ \\
push(x): Inserta el elemento x en el tope del stack. \\ \\
pop(): Remueve el elemento que se encuentra en el tope del stack.\\ \\  

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
stack<int> S;

//Agrega los números 0..9 a la pila
forn(i,10) S.push(i); 

//Imprime los primeros 4 elementos de la pila y los remueve
forn(i,4) {
  cout<<S.top()<<endl;
  Q.pop();
}
\end{verbatim}

}


\subsubsection*{priority\_queue}

Es un tipo de \emph{container adaptor} diseñado de forma tal que su primer elemento sea siempre el mayor elemento, según
una relación de orden dada. El adaptador \texttt{priority\_queue} encapsula un \emph{container}, proveyendo operaciones
específicas de acceso a sus elementos. Las operaciones de inserción y eliminación poseen un tiempo de ejecución de
$O(n \log n)$.
\\ \\
\subtitulo{Operaciones:} 
\\ \\
size(): Retorna la cantidad de elementos en la priority\_queue. \\ \\
top(): Retorna el elemento tope de la estructura, es decir, el mayor según la relación de orden dada. \\ \\
push(x): Agrega el elemento x a la priority\_queue. \\ \\
pop(): Remueve el elemento tope de la estructura. \\ \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}


struct comp {	
  bool operator() (const int& a, const int& b)
  {
    if (a%2!=b%2) return a%2;
    else return (a<b);
  }
}

int main ()
{
  
//Crea una priority_queue de int con vector<int> como estructura
//subyacente y un comparador definido por el usuario

  priority_queue< int, vector<int>, comp > pq;

  int nums[]= {15,260,553,246};
  
//Agrega los 4 elementos al priority_queue
  forn(i,4) pq.push(nums[i]);

//Imprime y remueve 4 elementos del priority_queue
  forn(i,4) {
    cout<<pq.top()<<" ";
    pq.pop();
    }

//Salida obtenida: "260 246 553 15" (primero los pares de mayor
// a menor y luego los impares de mayor a menor)

  return 0;
}
\end{verbatim}

}

\subsection*{Algoritmos}
% 

\subsubsection*{Ordenamiento: sort}

Ordenar los elementos de una colección es una de las operaciones más utilizadas.
Para esto, la {\em STL} ofrece la función {\tt sort}:
\\ \\
sort(inicio, fin): ordena los elementos en el intervalo de iteradores [inicio, fin). \\ \\
sort(inicio, fin, cmp): ordena los elementos en el intervalo de iteradores [inicio, fin) utilizando el comparador cmp. \\

% \marginpar {buscar paper intro-sort y agregar ref de wiki}
El algoritmo de ordenamiento implementado es el {\em introsort} \cite{introsort}, una combinación de {\em quicksort} y {\em heapsort}.
La idea es comenzar a ordenar los elementos mediante la técnica de {\em quicksort} y cuando la profundidad de la recursión alcanza un cierto límite
se usa {\em heapsort}. Esto asegura un tiempo de ejecución de $O(n \log n)$ en el peor caso y a su vez posee constantes bajas. \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
vi v;
// Genera un vector de 100 números aleatorios
forn(i,100) v.pb(rand() % 100);

// Ordena de forma ascendente el vector
sort(all(v));

// Ordena de forma descendente el vector
sort(rall(v));

// Definición de relación de orden
bool cmp(int a, int b) {
  if (a%2 != b%2) return a%2 == 0;
  return a < b;
}

// Ordena primero los pares y luego los impares
sort(all(v),cmp);
\end{verbatim}
}

\subsubsection*{Búsqueda binaria: lower\_bound, upper\_bound, binary\_search}

La librería estándar de C++ provee funciones para realizar búsqueda binaria:
\\ \\
lower\_bound(inicio, fin, x): devuelve un iterador en el rango [inicio,fin) que apunta al primer elemento mayor o igual a x. \\ \\
upper\_bound(inicio, fin, x): devuelve un iterador en el rango [inicio,fin) que apunta al primer elemento mayor a x. \\ \\
binary\_search(inicio, fin, x): devuelve un booleano indicando si x está presente en [inicio,fin). \\

Vale aclarar que todas las operaciones asumen que los elementos se encuentran ordenados. \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
// Genera un arreglo de números aleatorios...
vi v;
forn(i,100) v.pb(rand()%100);
// ... y lo ordena
sort(all(v));

const int BUSC = 77;

if (binary_search(all(v),BUSC)) {
  decl(primero, lower_bound(all(v), BUSC);
  decl(ultimo, upper_bound(all(v), BUSC);

  cout << "Primera aparicion: " << primero - v.begin() << endl;
  cout << "Última aparicion: " << ultimo - v.begin() << endl;
}
else
  cout << "No hay apariciones" << endl;
\end{verbatim}
}

\subsubsection*{Generando todas las permutaciones: next\_permutation}

bool next\_permutation(inicio, fin): reordena los elementos de [inicio,fin) de modo de obtener la siguiente permutación en orden lexicográfico.
Devuelve false si tal permutación no existe (se pasó como parámetro la lexicográficamente mayor).

Esta función se puede utilizar para iterar sobre todas las permutaciones de un conjunto de elementos.
Es un método sumamente eficiente ya que el tiempo amortizado de la operación {\tt next\_permutation} es $O(1)$.
La otra opción sería generar todas las permutaciones realizando {\em backtracking}, lo cual resulta más tedioso de programar. \\

\subtitulo{Ejemplo:}
{\small
\begin{verbatim}
// Bool chequea si 2 palabras son anagramas
bool anagrama(int n, char a[], char b[]) {
  sort(b,b+n);
  do {
    if (strcmp(a,b) == 0) return true;
  } while (next_permutation(b,b+n);
  return false;
}
\end{verbatim}
}

\section{Implementaciones compactas}

El estilo de programación propuesto en este capítulo nos permite generar código extremadamente compacto.
Para ilustrar este punto, a continuación ofrecemos implementaciones de algoritmos que resultan llamativamente breves y sencillas si hacemos
uso de estos ``trucos".

\subsubsection*{Algoritmo de Euclides (1 línea)}

\begin{verbatim}
int mcd(int a, int b) { return a ? mcd(b%a, a) : b; }
\end{verbatim}

Si $a$ es $0$, entonces $mcd(0,b) = b$ por lo tanto retornamos $b$.
En caso contrario, usamos la reducción $mcd(a,b) = mcd(a, b \mod a)$. 
El llamado recursivo a \verb|mcd(b%a, a)| se realiza de este modo para que el primer argumento sea el menor, si 
ordenáramos los parámetros al revés, el programa no finalizaría.
\newline

El operador ternario {\tt ?:} suele ser desaconsejado por su falta de claridad. Sin embargo, existen casos en los que la
complejidad de las expresiones implicadas resulta manejable y su uso permite un código más corto y simple. Éste es uno de esos casos.

\subsubsection*{Algoritmos de Floyd-Warshall (1 línea)}

Este sencillo algoritmo nos permite computar la distancia mínima entre todo par de nodos de un grafo en un tiempo de $O(n^3)$.

{\small
\begin{verbatim}
int n; // cantidad de nodos
int dist[MAXN][MAXN]; // matriz de distancias
....
// Floyd-Warshall
forn(k,n) forn(i,n) forn(j,n) 
  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 
\end{verbatim}
}
Con la utilización de la macro {\tt forn} y el hábito de condensar en una o pocas líneas
las operaciones que tiene una cierta unidad o cohesión lógica obtenemos una implementación en 1 línea.

El compilador {\em GCC} ofrece otro operador que hace el código incluso más corto: {\tt <?=}.
Las funciones {\tt min} y {\tt max} son también proveídas por operadores infijos. A saber, {\tt min(a,b)} es equivalente a {\tt a<?b} y
{\tt max(a,b)} puede notarse como {\tt a>?b}.
Los operadores {\tt <?=} y {\tt >?=} tienen una semántica parecida al resto de los operadores de operación-asignación como {\tt +=} o {\tt *=}. 
En particular {\tt a <?= b} tendrá el mismo efecto que {\tt a = min(a,b)}. Esto resulta particularmente conveniente para la operación de relajar 
arcos necesaria en algoritmos como {\em Dijkstra} y {\em Floyd-Warshall}.

Utilizando este operador, {\em Floyd-Warshall} toma la siguiente forma:
{\small
\begin{verbatim}
forn(k,n) forn(i,n) forn(j,n) dist[i][j] <?= dist[i][k] + dist[k][j];
\end{verbatim}
}

\subsubsection*{Estructura de datos {\em union-find} (4 líneas)}

{\small
\begin{verbatim}
int pre[MAXN];
void init() { forn(i,MAXN) pre[i] = i; }
void merge(int a, int b) { pre[a] = b; }
int find(int x) { return pre[x] = pre[x] == x ?  x : find(pre[x]); }
\end{verbatim}
}

Este es uno de los ejemplos más contundentes sobre los beneficios de la programación compacta que venimos exponiendo.
En apenas 4 líneas de código se puede implementar la estructura de datos de {\em union-find} con {\em path-compression} incluido.

Si bien esta implementación no realiza el chequeo y ajuste de {\em ranks} (altura de árboles), la sola utilización de {\em path compression}
hace que el algoritmo sea lo bastante eficiente para cualquier fin práctico dentro de las competencias.
\newline

El código utiliza un arreglo {\tt pre} donde se apunta al padre de cada nodo en la foresta (las raíces se apuntan a sí mismas).
La inicialización ({\tt init}) y la operaciones de combinación ({\tt merge}) resultan claras.

La operación de búsqueda del conjunto disjunto al que pertenece el elemento $x$ ({\tt find}) puede resultar más complicada de entender. 
La idea es que si $x$ es raíz de un árbol ({\tt pre[x] == x}), entonces éste será el representante del conjunto disjunto.
En caso contrario, el representante deseado será el mismo que el de su padre ({\tt pre[x]}).
El operador ternario {\tt ?:} nos permite obtener una expresión compacta de esta definición.

Por último, el resultado de dicha expresión se guarda en {\tt pre[x]} para realizar {\em path compression} y al mismo tiempo se retorna como resultado.

\subsubsection*{Longest Increasing Subsequence (7 líneas)}

Encontrar la subsecuencia creciente más larga dentro de una secuencia de $n$ elementos sujetos a una relación de orden total es un problema
muy conocido que puede resolverse utilizando programación dinámica.
Existe una solución muy sencilla que se ejecuta en un tiempo de $O(n^2)$.

En ocasiones es necesario dar con un algoritmo más eficiente, una solución más ingeniosa hace uso de búsqueda binaria para bajar el tiempo a 
$O(n \log n)$. Haciendo uso de la {\em STL} y algunas macros es posible implementar esta solución en pocas líneas.

\begin{verbatim}
int lis(vi v) {
  vi res;
  forn(i,si(v)) {
    decl(it, lower_bound(all(res, v[i])));
    if (it == res.end()) res.pb(v[i]); else *it = v[i];
  }
  return si(ret);
}
\end{verbatim}

Resulta una implementación directa del algoritmo mencionado. El uso de definiciones de tipo como {\tt vi}, macros como 
{\tt forn}, {\tt decl} y {\tt si}, y la búsqueda binaria implementada por {\em STL} ({\tt lower\_bound}) facilitan la tarea de codificación.

% perlitas
%   usar pair que tiene orden implícito
%  
% redefinición operadores (aritméticos para polinomios/matrices)
%   formateo de entrada: sscanf, stringstream
%   formateo de salida: iomanip, stdio (decimales sobre todo)
%     escupir debugueo por std error
% 
% struct NUNCA class
% templates: genericity
% 
% movimientos en tableros (caballo, 8 vecinos)


\chapter{Conclusiones y futuros trabajos}

%\begin{flushright}
%Somos lo que repetidamente hacemos. La excelencia, por lo tanto, no es un acto sino un hábito. 
%Saber popular
%\end{flushright}

Las competencias de programación representan un papel fundamental en la formación académica de una gran cantidad de alumnos alrededor del mundo, tanto
a nivel secundario como universitario. No forman parte del sistema educativo tradicional, sino que resultan en una herramienta complementaria, que
incentiva un modo de pensar diferente, más intuitivo e innovador.
\newline

A lo largo de los años, nuestro país ha obtenido buenos resultados en este tipo de competencias. Sin embargo, en los últimos años se ha podido observar
un incremento en la calidad y cantidad de equipos participantes en países que solían tener resultados no tan buenos como los nuestros, tales como
Bolivia y Perú. Creemos que esto se debe principalmente al gran apoyo que los estudiantes de estos países reciben de sus universidades, lo cual 
no sucede en la Argentina, especialmente fuera de Capital Federal. 

Para elevar el nivel de la región, es importante fortalecer los lazos entre los integrantes de la Comunidad. Como hemos mencionado en este trabajo, 
para poder lograr este objetivo, resulta de vital importancia la realización de Training Camps a nivel nacional y la utilización de listas de correo
para discutir problemas y compartir ideas en general.

Otro factor importante que puede favorecer a una mayor participación en nuestro país es que la sede de la instancia Regional de la ACM ICPC sea 
rotativa, en lugar de realizarse todos los años en Capital Federal, para así poder alcanzar a alumnos de todo el país. 
\newline

Es necesario que no se pierda el contacto entre los ex-participantes y los actuales. Las competencias de programación poseen una amplia variedad
de características que las diferencias de otras actividades académicas. Es por esta razón que las personas que han adquirido una gran experiencia en 
este tipo de certámenes resultan ideales para preparar a los nuevos participantes, ya que pueden guiarlos de una manera mucho más adecuada.
Por último, consideramos que sería un paso clave formar espacios para la práctica y el entrenamiento dentro de cada universidad, llegando de
esta manera a alumnos que estén interesados en participar pero no hayan encontrado alguien que les pueda ayudar en su preparación.
\newline

En este trabajo se intentó proveer al lector de una guía de iniciación a las competencias de programación. Futuros trabajos podrán realizar una 
introducción teórica a temas claves para el desarrollo de problemas, tales como Programación dinámica, Teoría de grafos, String Matching,
Geometría computacional, etc. A su vez, es posible incluir un análisis de problemas más exhaustivo que el desarrollado en el presente trabajo.




\appendix
\chapter{Enunciados}

En este apéndice listamos una colección de enunciados de problemas de competencias anteriores.
Éstas son presentadas exactamente en el mismo formato que en el contexto real de competencia para que el lector
logre formar una idea de qué tipo de enunciados puede encontrar.
\newline

Primero presentamos enunciados de las pruebas de carácter presencial: {\em ACM} e {\em IOI}. 
En el contexto de competencias, estos enunciados serán dados en formato impreso.
Para ilustrar los diferentes tipos de problemas que pueden encontrarse en un examen de {\em IOI} agregaremos uno de tipo {\em batch},
una tarea interactiva y uno con entrada no-secreta.

Luego mostraremos el formato de competencias cuyos problemas son presentados mediante una interfaz web: {\em Google Code Jam}, {\em Topcoder} y 
{\em Codeforces}. 


\includepdf[pages=19-20]{./enunciados/acm1.pdf}
\includepdf[pages=-]{./enunciados/ioi1.pdf}
\includepdf[pages=-]{./enunciados/ioi2.pdf}
\includepdf[pages=-]{./enunciados/ioi3.pdf}
\includepdf[pages=-]{./enunciados/codejam.pdf}
\includepdf[pages=-]{./enunciados/topcoder.pdf}
\includepdf[pages=-]{./enunciados/codeforces.pdf}

 

\begin{thebibliography}{9}

%%%% PAPERS

\bibitem{boyer}
Boyer, Robert S., Moore, J.Strother. 
{\em Fast string searching algorithm},
1977

\bibitem{kmp}
Donald E. Knuth, James H. Morris, Jr., Vaughan R. Pratt. 
{\em Fast Pattern Matching in Strings},
1977

\bibitem{aho}
A. V. Aho and M. J. Corasick. 
{\em Efficient string matching: An aid to bibliographic search}. Communications of the ACM,18(6):333–340, 
1975.

\bibitem{graham}
R. L. Graham 
{\em An efficient algorithm for determining the convex hull of a finite planar set},
1972

\bibitem{andrew}
A. M. Andrew.
{\em Another efficient algorithm for convex hulls in two dimensions},
1979

\bibitem{teamwork}
Saman Amirpour Amraii. 
{\em Observations on Teamwork Strategies in the ACM International Collegiate Programming Contest}. Publicado en Magazine Crossroads,
2007

\bibitem{introsort}
David R. Musser
{\em Introspective Sorting and Selection Algorithms},
1997



%%%%% LIBROS
\bibitem{cormen}
  T.H. Cormen, C.E. Leiserson, R.L. Rivest, S. Stein. 
  \emph{Introduction to Algorithms}.
  MIT Press,
  2nd Edition,
  1990.

\bibitem{sedgewick}
R. Sedgewick.
\emph{Algorithms}.
Addison-Wesley,
1983

\bibitem{concrete}
R.L. Graham, D.E. Knuth, O.Patashnik. 
\emph{Concrete Mathematics}. 
Addison-Wesley,
1989. 

\bibitem{taocp} 
Donald E. Knuth. 
{\em The Art of Computer Programming}.
Vol.1-3. Addison-Wesley, 3d ed., 
1997

\bibitem{halim}
A.S. Arefin, S. Halim, L. Rahman.
{\em Art of Programming Contest}.
Gyankosh Prokashoni, Bangladesh,
2nd Edition,
2006

\bibitem{skiena}
Steven S. Skiena.
{\em The Algorithm Design Manual}.
Springer-Verlag,
1997

%%%%%% SITIOS
\bibitem{icpc}
  ACM International Collegiate Programming Contest
  http://cm.baylor.edu/welcome.icpc

\bibitem{acm}
  Association for Computing Machinery
  http://www.acm.org/

\bibitem{ioi}  
  International Olympiad in Informatics
  http://ioinformatics.org

\bibitem{topcoder}
  Topcoder
  http://www.topcoder.com/tc

\bibitem{codejam}
  Google Code Jam
  http://code.google.com/codejam
  
\bibitem{codeforces}
  Codeforces
  http://codeforces.com/

\bibitem{usacotrain}
  Usaco Training Gateway,
  train.usaco.org/usacogate

\bibitem{stlref}
Hewlett-Packard Company.
{\em Standard Template Library Programmer's Guide}.
1994.
Disponible en http://www.sgi.com/tech/stl/ (accedida en noviembre de 2011)
    

\end{thebibliography}

\end{document}
